Từ Selection Sort đến Quick Sort

Trên bàn có sáu phiếu điểm, theo thứ tự 7, 3, 5, 3, 9, 1. Bạn cần xếp chúng từ thấp đến cao để đọc tên những người có cùng mức điểm liền nhau. Đặt phiếu 1 lên đầu khá dễ. Nhưng sau lần dịch chuyển ấy, bạn đã biết chắc điều gì về năm phiếu còn lại?

Hai đoạn Java cùng có hai vòng lặp lồng nhau có thể phản ứng rất khác khi nhận một danh sách gần có thứ tự. Ta sẽ xem phần công việc còn lại sau mỗi lượt để hiểu sự khác biệt đó.

Đây là bộ phiếu mô phỏng dùng xuyên bài. Mỗi phiếu có thêm một nhãn để ta không đánh mất người đứng sau con số:

7_A   3_B   5_C   3_D   9_E   1_F

3_B và 3_D có cùng điểm nhưng là hai bản ghi khác nhau. Nếu sinh viên B nộp trước D, ta có thể muốn giữ thứ tự ấy khi xếp theo điểm. Vì vậy, một kết quả gồm sáu số 1 tuy không giảm vẫn là kết quả sai: chương trình đã làm mất dữ liệu. Một hàm sort đúng phải tạo ra thứ tự cần tìm và giữ nguyên các bản ghi đầu vào.

Các animation lấy trạng thái từ Java chạy thật. Chữ cái đi cùng phiếu qua mỗi lần di chuyển; hai bộ đếm ghi số lần so sánh key và số lần ghi vào array dữ liệu, không tính biến tạm hay metadata để vẽ hình. Có thể mở bản MP4 có nút dừng và tua khi giảng trên lớp. File Sorting.java chứa bản code gọn để thực hành; SortingLab.java thêm bộ đếm, identity và test.

Tại sao phải bỏ công sắp xếp?

Nếu chỉ hỏi phiếu nào có điểm thấp nhất, ta quét một lượt là đủ. Sort toàn bộ để trả lời đúng một câu ấy thường làm nhiều việc hơn cần thiết. Nhưng khi liên tục cần tìm một mức điểm, liệt kê một khoảng điểm, ghép hai danh sách hoặc gom những bản ghi bằng nhau, thứ tự đã tạo ra giúp ta tránh dò lại từng phần tử từ đầu.

Chẳng hạn, sau khi xếp tăng dần, nếu đang đọc tới điểm 7 thì không cần tiếp tục tìm một phiếu điểm 3 ở phía sau. Binary Search cũng dùng thông tin tương tự để bỏ một nửa vùng tìm kiếm. Chi phí sort là tiền công trả trước cho những lần đọc sau; có nên trả hay không còn tùy công việc.

Ta sẽ xếp ngay trên array, thay vì tạo một danh sách kết quả khác. Vấn đề trở thành: có thể giữ phần nào trong array ở một trạng thái đáng tin, rồi mở rộng phần ấy bằng những thao tác nhỏ nào?

Selection Sort: chốt từng vị trí

Một cách làm tự nhiên là tìm phiếu nhỏ nhất trong cả chồng, đưa nó lên đầu, rồi không động vào vị trí đầu nữa. Ở lượt tiếp theo, chỉ tìm trong phần còn lại. Bạn không cần đoán vị trí của tất cả mọi người cùng lúc; mỗi lượt giải quyết một chỗ.

Với sáu phiếu đang có, lượt đầu tìm được 1_F và đổi chỗ nó với 7_A:

Trước: 7_A  3_B  5_C  3_D  9_E  1_F
Sau:   1_F  3_B  5_C  3_D  9_E  7_A
       xong |------ chưa xếp -------|

Phiếu 1 không chỉ nhỏ hơn phiếu bên cạnh. Nó nhỏ nhất trong tất cả phiếu, nên đã đứng ở vị trí cuối cùng của mình. Lượt sau có thể bỏ qua nó.

Sau i lượt, đoạn bên trái chứa đúng i phiếu nhỏ nhất theo thứ tự tăng dần. Trong thuật toán, điều luôn giữ đúng ở một mốc của vòng lặp như vậy gọi là loop invariant. Nó vừa là cách đọc code, vừa là lời giải thích vì sao code làm đúng.

public static void selectionSort(int[] a) {
    for (int i = 0; i + 1 < a.length; i++) {
        int min = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[min]) min = j;
        }
        swap(a, i, min);
    }
}

Ở đầu vòng ngoài, [0, i) đã xong. Vòng trong tìm chỉ số min trong [i, n). Đổi chỗ a[i] với a[min] mở rộng đoạn đã xong thêm một phần tử. Ban đầu i=0, đoạn ấy rỗng nên điều kiện đúng; cuối cùng chỉ còn một phần tử chưa xét, và nó buộc phải là phần tử lớn nhất còn lại.

Các bản code trong bài dùng chung hàm đổi chỗ này:

private static void swap(int[] a, int i, int j) {
    if (i == j) return;
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

Điều đáng chú ý xảy ra khi chồng phiếu đã có thứ tự. Selection vẫn phải quét toàn bộ phần còn lại để chắc rằng phần tử ở đầu là nhỏ nhất. Với sáu phiếu, số lần so sánh vẫn là 5 + 4 + 3 + 2 + 1 = 15. Nhìn tổng quát:

\[C(n)=(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}2.\]

Ta đếm được từ chính các cận của vòng lặp, không cần bấm giờ. Code ở trên bỏ qua việc tự đổi một phần tử với chính nó, nên một input đã sorted có thể không cần ghi array lần nào nhưng vẫn chịu đủ số so sánh ấy. Đây là hai loại công việc khác nhau. Tài liệu Princeton cũng phân biệt chi phí so sánh với việc di chuyển dữ liệu khi phân tích Selection Sort. ^[1]

Insertion Sort: có thứ tự chưa có nghĩa là đã đứng yên

Bây giờ đổi cách làm. Giữ một hàng phiếu đã có thứ tự ở bên trái; mỗi lần lấy phiếu tiếp theo rồi chen nó vào đúng chỗ trong hàng đó. Bạn có thể đã làm thao tác này khi xếp các lá bài trên tay, dù chưa từng gọi nó là một thuật toán.

Hàng ban đầu chỉ có 7_A. Nhận 3_B, bạn giữ nó trên tay, dịch 7_A sang phải rồi đặt 3_B vào chỗ trống. Nhận 5_C, bạn lại dịch 7_A, nhưng dừng khi chạm 3_B:

7_A | 3_B  5_C  3_D  9_E  1_F
3_B  7_A | 5_C  3_D  9_E  1_F
3_B  5_C  7_A | 3_D  9_E  1_F

Trong Selection, phiếu ở đoạn bên trái đã có vị trí cuối cùng. Trong Insertion, đoạn bên trái chỉ có thứ tự với những phiếu đã nhận. Khi 1_F tới muộn, mọi phiếu trong hàng vẫn phải dịch sang phải. Hai invariant trông gần giống nhau, nhưng không cho phép cùng một kết luận.

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

Biến key giữ phiếu đang chen. Nếu ghi đè a[i] trước khi giữ bản sao đó, ta có thể đánh mất phiếu. Sau mỗi lần dịch a[j] sang a[j+1], chỗ trống chuyển sang trái. Khi vòng lặp dừng, j trỏ vào phiếu nhỏ hơn hoặc bằng key, hoặc bằng -1 nếu không còn phiếu nào bên trái. Bởi vậy vị trí cần ghi là j+1.

Điều kiện j >= 0 phải đứng trước a[j] > key. Java đánh giá && từ trái sang phải và không tính vế sau khi vế trước sai. Đảo hai vế sẽ đọc a[-1] khi key nhỏ nhất đi hết về đầu.

Một input đã tăng dần khiến mỗi lượt so sánh key với phần tử ngay trước nó rồi dừng. Tổng cộng chỉ n-1 key comparisons. Với input giảm dần và các key khác nhau, lượt thứ i phải dịch cả i phần tử trước đó, đưa tổng công việc trở lại bậc hai.

Muốn nói chính xác hơn về input "gần có thứ tự", ta có thể đếm inversions: những cặp nằm ngược với thứ tự cần có. Trong [3, 1, 2], đó là cặp (3,1) và (3,2). Mỗi lần Insertion dịch một phần tử lớn hơn key sang phải, nó sửa đúng một inversion. Một array dài nhưng chỉ sai vị trí vài cặp có thể cần rất ít lần dịch; chỉ đếm số vòng for và while trong source sẽ bỏ lỡ điều này.

Hai phiếu điểm 3

Khi 3_D chen vào đoạn [3_B, 5_C, 7_A], nó đi qua 7 và 5 rồi dừng sau 3_B. Dấu > trong điều kiện là lựa chọn có chủ ý: phần tử bằng key không bị dịch. Thứ tự B trước D được giữ lại.

Ta gọi một cách sort giữ thứ tự tương đối của các bản ghi bằng key là stable. Insertion ở trên có tính chất này; bản tối ưu InsertionX của Princeton cũng giữ stability dù giảm thao tác di chuyển bằng cách khác. ^[2]

Selection thì không đảm bảo. Input chính tình cờ chưa làm nó đảo hai phiếu điểm 3, nên cần một phản ví dụ nhỏ hơn để nhìn thấy vấn đề:

2_A  2_B  1_C
1_C  2_B  2_A    <- đổi 1_C với 2_A

Một test không làm thuật toán đảo thứ tự không chứng minh thuật toán stable. Ngược lại, chỉ cần một input như trên là đủ bác bỏ lời khẳng định "Selection luôn giữ thứ tự".

Bubble Sort và quãng đường một phiếu phải đi

Bạn cũng có thể chỉ cho hai người đứng cạnh nhau đổi chỗ nếu họ đang ngược thứ tự. Quét từ trái sang phải, phiếu lớn nhất trong phần vừa xem sẽ dần đi sang phải. Kết thúc một lượt, nó đã tới cuối vùng đang xét.

Trong input của chúng ta, phiếu 9 gần cuối nên tới đích khá nhanh. Phiếu 1 ở tận cuối lại phải đi về trái qua nhiều lượt. Bubble không được nhấc phiếu 1 lên rồi đặt thẳng vào đầu như Selection; nó chỉ dịch qua từng người hàng xóm.

public static void bubbleSort(int[] a) {
    for (int end = a.length - 1; end > 0; end--) {
        boolean changed = false;
        for (int j = 0; j < end; j++) {
            if (a[j] > a[j + 1]) {
                swap(a, j, j + 1);
                changed = true;
            }
        }
        if (!changed) return;
    }
}

Sau một pass, max của vùng active đứng ở end, nên lần sau giảm end. Trong một pass mà không có swap, mọi cặp kề nhau trong vùng active đã có thứ tự. Kết hợp với suffix đã cố định, ta biết toàn array có thứ tự và được phép dừng ngay.

Biến changed vì thế phải đặt lại thành false ở đầu mỗi pass. Nếu đặt nó một lần trước vòng ngoài, một swap ở đầu chương trình sẽ khiến các pass sau không bao giờ dùng được điều kiện dừng sớm.

Bubble trong bài cũng dùng >, nên hai phiếu bằng key không đổi chỗ trực tiếp. Để vượt nhau trong một thuật toán chỉ đổi hàng xóm, chúng buộc phải đổi chỗ trực tiếp tại một thời điểm nào đó; vì điều ấy không xảy ra, relative order được giữ. Nếu thay > bằng >=, kết quả số vẫn sorted nhưng stability có thể mất, và một hàng toàn key bằng nhau lại bị đổi qua đổi lại vô ích.

Bubble giúp nhìn rõ cái giá của việc chỉ được đổi hàng xóm. Nó hữu ích để học invariant và inversion; không vì thế mà ta nên chọn nó mặc định để sort dữ liệu trong ứng dụng.

Quick Sort: phân đúng phía trước khi xếp đúng chỗ

Cả ba cách trên đều làm một phần nhỏ của kết quả tiến thêm sau mỗi lượt. Quick Sort chọn một phiếu làm mốc, gọi là pivot, rồi phân loại các phiếu còn lại theo mốc ấy. Những phiếu nhỏ hơn đi về một phía; những phiếu lớn hơn hoặc bằng đi về phía kia.

Chưa cần bên trái có thứ tự. Chỉ cần mọi phiếu bên trái nhỏ hơn pivot, mọi phiếu bên phải không nhỏ hơn pivot, rồi đặt pivot vào giữa hai vùng. Sau đó hai nhóm có thể tự giải quyết công việc nội bộ. Không có phiếu nào ở nhóm trái phải đi qua pivot để sang nhóm phải nữa.

Phiên bản dưới đây dùng Lomuto partition, lấy phần tử cuối làm pivot và không shuffle. Với input 7,3,5,3,9,1, pivot đầu tiên là 1. Không có ai nhỏ hơn nó, nên nó về đầu và để lại một nhóm năm phiếu bên phải. Ngay ví dụ đầu đã cho thấy partition không hứa sẽ chia đôi đều.

public static void quickSort(int[] a) {
    quickSort(a, 0, a.length - 1);
}

private static void quickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}

private static int partition(int[] a, int lo, int hi) {
    int pivot = a[hi];
    int boundary = lo;
    for (int scan = lo; scan < hi; scan++) {
        if (a[scan] < pivot) {
            swap(a, boundary, scan);
            boundary++;
        }
    }
    swap(a, boundary, hi);
    return boundary;
}

Đọc partition bằng ba chỉ số lo, boundary, scan sẽ dễ hơn học thuộc các dòng swap. Trong lúc quét, pivot vẫn nằm ở hi; phần còn lại chia thành ba vùng:

lo               boundary         scan                  hi
| nhỏ hơn pivot  | >= pivot       | chưa phân loại       | pivot |

Nếu a[scan] < pivot, swap nó vào đầu vùng lớn hơn hoặc bằng, rồi tăng boundary. Phần tử bị đổi ra vị trí scan vốn đã thuộc vùng lớn hơn hoặc bằng, nên không cần xét lại. Nếu a[scan] >= pivot, để nguyên rồi tăng scan; vùng ấy tự mở rộng thêm một phần tử.

Khi scan chạm hi, không còn phần tử chưa phân loại. Swap pivot vào boundary, ta có:

[lo, p) < pivot     a[p] = pivot     (p, hi] >= pivot

Hai range gọi đệ quy bỏ hẳn p: [lo,p-1] và [p+1,hi]. Đây là điều làm công việc nhỏ đi, kể cả khi một phía rỗng. Nếu lỡ gọi lại nguyên range cũ trong trường hợp pivot rơi ở đầu hoặc cuối, chương trình có thể đệ quy mãi đến khi hết stack.

Một lỗi khó nhận ra hơn là lấy công thức gọi đệ quy của Lomuto ghép với một hàm partition kiểu khác. Source Quick.java của Princeton shuffle trước rồi dùng hai con trỏ quét từ hai phía, khác với Lomuto. Khi tham khảo một bản Quick Sort khác, hãy đọc xem hàm partition trả về vị trí của pivot hay chỉ là ranh giới chia vùng, rồi mới chọn hai range tiếp theo. ^[3]

Vì sao có lúc nhanh, có lúc tệ?

Mỗi partition của range dài n làm n-1 key comparisons. Nếu nó chia thành hai phần gần bằng nhau, mức tiếp theo xử lý hai range có tổng kích thước gần n. Mỗi mức làm công việc bậc n; giảm đôi liên tiếp tạo ra bậc log n mức. Từ đó có chi phí bậc n log n.

Nhưng khi lần nào cũng chia thành 0 và n-1, công việc là:

\[T(n)=T(n-1)+(n-1).\]

Đó lại là tổng n(n-1)/2. Hãy chạy code trên một array đã tăng dần: pivot luôn là phần tử lớn nhất, mọi phần tử còn lại dồn vào nhóm trái. Code không cần swap thật vì tất cả đều là self-swap, nhưng vẫn so sánh rất nhiều và đệ quy sâu.

Trường hợp toàn phần tử bằng nhau cũng gây vấn đề cho bản Lomuto dùng <: không phần tử nào vào nhóm nhỏ hơn, nên pivot luôn về đầu. Đổi < thành <= chỉ chuyển cả đám sang phía kia, không làm hai nhóm cân hơn. Shuffle cũng không giúp nếu mọi key đều giống nhau.

Khi dữ liệu có nhiều key trùng, 3-way partition tạo ba nhóm nhỏ hơn, bằng và lớn hơn pivot. Nhóm bằng đã xong, không bị lôi vào lời gọi đệ quy tiếp theo. Source Quick3way.java thể hiện rõ lựa chọn này. ^[4]

Đếm lại trên cùng sáu phiếu

Khi chạy từng thuật toán trên một bản sao riêng của input ban đầu, SortingLab cho kết quả sau:

Insertion dịch chín lần rồi ghi key trở lại năm lần, thành 14 writes. Bubble có chín lần swap, mỗi lần ghi hai ô, thành 18. Cả hai sửa chín inversions của input, nhưng không di chuyển bằng cùng một thao tác.

Selection chỉ cần ba swap thật ở ví dụ này. Con số thấp đó không giúp nó giảm số lần quét tìm min. Quick dùng ít writes hơn Insertion trong input này, nhưng ta vừa tìm được input sorted khiến nó so sánh nhiều hơn hẳn.

Bảng thứ hai chỉ đếm key comparisons. Dữ liệu đầy đủ có cả array writes. Chưa có phép đo wall-clock được kiểm soát, nên mình không dùng bảng để kết luận thuật toán nào chạy nhanh nhất trên máy của bạn. Chi phí một comparison, cách CPU truy cập bộ nhớ, kích thước dữ liệu và JIT còn ảnh hưởng thời gian thực.

Tổng hợp chi phí của các bản code vừa chạy:

Bộ nhớ ở đây tính cho Sorting.java, không tính array đầu vào và không tính bộ ghi trace của SortingLab. Expected Θ(n log n) của Quick Sort cần giả thiết thích hợp, chẳng hạn thứ tự ngẫu nhiên của các key khác nhau. Nó không phải bảo đảm cho mọi input của hàm quickSort vừa viết.

Khi cần một bảo đảm khác

Merge Sort chia array thành hai phần, sort từng phần rồi merge. Trong lúc merge, chỉ phải so sánh hai đầu của hai hàng đã có thứ tự. Nếu bằng nhau thì lấy từ hàng bên trái trước, nhờ đó bản merge này giữ stability. Bản top-down dùng array phụ của Princeton có worst-case Θ(n log n) và cần O(n) bộ nhớ phụ. ^[5]

Heap Sort có thể nối với phần heap đã học: dựng max-heap, lấy phần tử lớn nhất đổi xuống cuối, thu nhỏ heap rồi khôi phục tính chất heap. Heap không chứa mọi phần tử theo thứ tự tăng hay giảm; nó chỉ giữ đủ thông tin để lấy max hiệu quả. Bản iterative trong nguồn có worst-case Θ(n log n), O(1) bộ nhớ phụ và không stable. ^[6]

Hai lựa chọn ấy giải quyết những ưu tiên khác nhau. Nếu cần giữ thứ tự bản ghi bằng key, phải kiểm tra stability. Nếu không có chỗ cho array phụ lớn, phải kiểm tra cách thuật toán dùng bộ nhớ. Nếu input có thể được sắp xếp theo một cách bất lợi, một bảo đảm worst-case đáng quan tâm hơn một kết quả trung bình đẹp.

Trong chương trình Java thông thường, nên đọc contract của thư viện trước khi tự viết lại sort. Arrays.sort cho object array đảm bảo stable. Java SE 24 mô tả implementation của overload này theo hướng stable, adaptive mergesort, nhưng tên thuật toán trong implementation note không phải điều mọi JDK buộc giữ mãi. Đừng suy từ đó rằng mọi overload cho primitive array có cùng contract. ^[7]

Ví dụ này chạy được từ StudentSortExample.java:

Arrays.sort(students, Comparator.comparingInt(s -> s.score));

Với các bản ghi mô phỏng An:7, Binh:3, Chi:5, Dung:3, Em:9, Phuc:1, output là:

[Phuc:1, Binh:3, Dung:3, Chi:5, An:7, Em:9]

Binh vẫn đứng trước Dung. Khi chuyển từ int[] sang các bản ghi thực, chữ "stable" mới hiện ra thành một yêu cầu mà người dùng có thể nhận thấy.

Đào sâu: vì sao không cứ so sánh ít hơn n log n?

Giả sử có n key khác nhau và thuật toán chỉ biết thứ tự của chúng qua các phép so sánh. Có n! thứ tự đầu vào. Ta có thể hình dung thuật toán như một cây quyết định: mỗi phép so sánh rẽ sang một trong hai nhánh, mỗi lá xác định thứ tự cần trả về.

Một cây nhị phân cao h có nhiều nhất 2^h lá. Muốn phân biệt đủ các thứ tự, cần:

\[n!\le 2^h\quad\Rightarrow\quad h\ge\log_2(n!).\]

Không cần công thức xấp xỉ khó để thấy bậc của nó. Với n chẵn, nửa cuối các thừa số của n! đều ít nhất bằng n/2, nên:

\[\log_2(n!)\ge\frac n2\log_2\frac n2.\]

Mặt khác, n! <= n^n, nên log₂(n!) <= n log₂ n. Cận dưới và cận trên có cùng bậc: Θ(n log n). Trường hợp n lẻ làm tròn số thừa số, không đổi kết luận về bậc tăng.

Đây là cận dưới worst-case cho comparison sorting với key khác nhau, không phải lời tiên tri về mọi bài toán sắp xếp. Nếu biết key là số nguyên trong một miền nhỏ và dùng thông tin ấy để đếm hay phân phối, ta đã khai thác thêm cấu trúc ngoài mô hình chỉ so sánh. Vì thế Counting Sort không mâu thuẫn với lập luận này.

Tự chạy, rồi thử làm code sai

Tải Sorting.java, SortingLab.java và StudentSortExample.java vào cùng một thư mục. Với JDK 9 trở lên, có thể kiểm tra khả năng biên dịch cho Java 8 bằng:

javac --release 8 -Xlint:all,-options -Werror *.java
java SortingLab test
java SortingLab metrics
java StudentSortExample

Nếu đang dùng JDK 8, bỏ --release 8 và dùng javac -Xlint:all -Werror *.java. Các test trong bài đã chạy trên JDK 24; target bytecode là Java 8.

Test suite duyệt mọi array dài 0 đến 7 trên tập key {-1,0,1}, thêm các array ngẫu nhiên fixed seed và các số ở biên kiểu int. Tổng cộng 15.124 tổ hợp input/algorithm được kiểm tra với cả bản gọn và bản có trace. Với mỗi lần sort, suite đối chiếu output với Arrays.sort, kiểm tra từng identity còn nguyên và kiểm tra stability của Insertion/Bubble. Nó còn đối chiếu công thức đếm phép toán trên nhiều kích thước input.

Để nhìn một lỗi rõ hơn, thử sửa đúng một dòng rồi dự đoán test nào sẽ thất bại:

1. Trong Insertion, dùng a[j] >= key. Các số còn sorted không? Điều gì xảy ra với identity?
2. Trong Bubble, bỏ việc đặt lại changed=false ở đầu pass. Thuật toán còn đúng không, và bạn mất điều gì?
3. Trong Quick, thử dùng [lo,p] làm range trái. Với input nào nó không nhỏ đi?
4. Với Selection, giữ nguyên thuật toán nhưng thay input bằng [2_A,2_B,1_C]. Lời khẳng định nào trong ba lời "sorted", "giữ đủ bản ghi", "stable" bị bác bỏ?

Khi quay lại chồng phiếu ban đầu, ta vẫn muốn đọc 1,3,3,5,7,9. Nhưng giờ có thêm những câu hỏi cụ thể: hai phiếu điểm 3 đứng theo thứ tự nào, phần nào đã cố định, và công việc gì còn phải làm nếu có thêm một phiếu mới. Nếu cả chồng đã xếp xong và bạn vừa nhận thêm một phiếu, thao tác chen nó vào hàng có lẽ đã hiện ra trước khi bạn kịp nhớ tên Insertion Sort.

Bình