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: 15, 13, 18, 19, 17, 12, 16, 14 What is the list after it is partitioned with low = 0 and up = n-1?

Đáp án đúng: "12, 13, 14, 15, 17, 19, 16, 18". Chốt là x bằng a[low] tức 15, i bắt đầu ở 0, j ở 7. Vòng một: i chạy lên và dừng ở 18 vì 18 lớn hơn 15, j dừng ngay ở 14 vì 14 không lớn hơn 15, đổi chỗ hai số đó được 15, 13, 14, 19, 17, 12, 16, 18. Vòng hai: i dừng ở 19, j lùi qua 18 và 16 rồi dừng ở 12, đổi chỗ được 15, 13, 14, 12, 17, 19, 16, 18. Vòng ba: i dừng ở 17, j lùi qua 19 và 17 rồi về 12, lúc này i đã vượt j nên không đổi chỗ và vòng lặp dừng; bước cuối đổi a[low] là 15 với a[j] là 12. "12, 13, 15, 14, 17, 19, 16, 18" để 15 trước 14, nghĩa là chốt không về đúng vị trí phân hoạch của nó. "12, 13, 14, 15, 16, 17, 19, 18" đã sắp lại cả phần bên phải chốt. "12, 13, 14, 15, 17, 16, 18, 19" cũng vậy, trong khi một lượt phân hoạch chỉ bảo đảm bên trái chốt không lớn hơn chốt và bên phải không nhỏ hơn, chứ không sắp xếp nội bộ hai phần.