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: 5, 3, 8, 9, 7, 2, 6, 4 What is the list after it is partitioned with low = 0 and up = n-1?

Đáp án đúng: "2, 3, 4, 5, 7, 9, 6, 8". Chốt là x bằng a[0] tức 5; i dò từ đầu mảng và dừng ở phần tử lớn hơn 5, j dò từ cuối mảng và dừng ở phần tử nhỏ hơn hoặc bằng 5, rồi đổi chỗ hai phần tử đó. Trên 5, 3, 8, 9, 7, 2, 6, 4: i dừng ở 8, j dừng ở 4, đổi được 5, 3, 4, 9, 7, 2, 6, 8; tiếp tục i dừng ở 9, j dừng ở 2, đổi được 5, 3, 4, 2, 7, 9, 6, 8; lượt ba i dừng ở 7 còn j lùi về đúng số 2, hai con trỏ đã vượt nhau nên vòng lặp dừng; cuối cùng đổi chốt 5 với số 2 tại vị trí j, cho 2, 3, 4, 5, 7, 9, 6, 8 với 2, 3, 4 ở trái chốt và 7, 9, 6, 8 ở phải. Vì vậy "2, 3, 5, 4, 7, 9, 6, 8" sai vì nó đưa chốt về ô thứ ba, tức đổi chốt với một j lùi chưa đủ; "2, 3, 4, 5, 6, 7, 9, 8" sai vì nó sắp lại phần bên phải chốt; "2, 3, 4, 5, 7, 6, 8, 9" cũng sai vì vậy, một lần phân hoạch chỉ chia hai phía so với chốt và để nguyên trật tự nội bộ 7, 9, 6, 8.