Partitioning is a technique used in quicksort. The following is a partition pseudocode for sorting from smallest to largest: partition the array a from index low to index up x := a[low], i=low, j=up do increase i and stop at i, where a[i]>x decrease j and stop at j, where a[j]<=x if(i<j) swap a[i] with a[j] while(i<j) swap a[low] with a[j] Consider the list of eight integers (n=8) below: 7, 4, 10, 11, 9, 3, 8, 6 What is the list after it is partitioned with low = 0 and up = n-1?

Đáp án đúng: "3, 4, 6, 7, 9, 11, 8, 10". Chốt là x = a[low] = 7, rồi dò hai đầu: i tiến tới phần tử đầu tiên lớn hơn 7, j lùi tới phần tử đầu tiên không lớn hơn 7, hai bên gặp cặp sai chỗ thì đổi chỗ. Trên 7, 4, 10, 11, 9, 3, 8, 6: i dừng ở 10, j dừng ở 6 (phần tử cuối, vì 6 không lớn hơn 7), đổi chỗ được 7, 4, 6, 11, 9, 3, 8, 10; vòng hai i dừng ở 11, j dừng ở 3, đổi chỗ được 7, 4, 6, 3, 9, 11, 8, 10; vòng ba i dừng ở 9 còn j lùi về đúng ô của số 3 nên hai chỉ số đã vượt nhau và không đổi gì nữa. Cuối cùng đổi chốt 7 với a[j] = 3, cho 3, 4, 6, 7, 9, 11, 8, 10, trong đó mọi số bên trái 7 đều nhỏ hơn 7 và mọi số bên phải đều lớn hơn 7 — đúng mục tiêu của một lần phân hoạch. "3, 4, 7, 6, 9, 11, 8, 10" để 6 nằm bên phải chốt dù 6 nhỏ hơn 7. "3, 4, 6, 7, 9, 8, 10, 11" và "3, 4, 6, 7, 8, 9, 11, 10" đều đã sắp lại phần bên phải chốt, việc mà một lần phân hoạch chưa làm.