Quadratic sorts — Bubble, Selection, Insertion sort

TL;DR: Ba quadratic sort — Bubble, Selection, Insertion — đều O(n²) trung bình, nhưng khác nhau rõ về đặc tính thực tế. Bubble sort gần như không có lý do dùng trong production. Selection sort có ưu điểm duy nhất là tối thiểu số lần swap (đúng n-1 lần) nhưng không adaptive và không stable. Insertion sort là algorithm được TimSort gọi cho subarray dưới 32-47 phần tử: stable, adaptive O(n+d) với d là số inversion, online — ba đặc tính khiến nó vẫn xuất hiện trong production library dù O(n²) về mặt lý thuyết. Constants matter khi n nhỏ.

Bubble sort là ví dụ đầu tiên về sorting algorithm trong hầu hết giáo trình đại học — và cũng là thứ đầu tiên bị gạch chân đỏ trong code review. O(n²), chậm, không có lý do dùng trong production. Câu chuyện kết thúc ở đó.

Nhưng mở file DualPivotQuicksort.java trong OpenJDK, bạn thấy dòng:

-- DualPivotQuicksort.java (OpenJDK):
-- Use insertion sort for small arrays
-- if (right - left + 1 < INSERTION_SORT_THRESHOLD) ...

INSERTION_SORT_THRESHOLD hiện tại là 47. Với subarray dưới 47 phần tử, JDK bỏ qua Dual-Pivot Quicksort và gọi thẳng Insertion sort. Python's TimSort và C++ IntroSort làm tương tự. Vì sao một algorithm O(n²) lại xuất hiện trong production library của ngôn ngữ lập trình chính?

Bài này so sánh 3 quadratic sort, pseudocode đầy đủ, benchmark thực tế, và lý giải vì sao Insertion sort là adaptive và vẫn xuất hiện trong production library.

1. Analogy — Ba cách sắp bài tay

Hình dung bạn có 10 quân bài xáo trộn, cần sắp theo thứ tự. Ba người bạn mỗi người dùng cách khác nhau:

Bubble — so từng cặp kế nhau, đổi chỗ nếu sai: Quét từ trái qua phải, so quân thứ i và i+1. Nếu sai thứ tự thì đổi. Sau một lượt, quân lớn nhất "nổi" lên cuối — như bong bóng nổi lên mặt nước. Quét lại, lần này bỏ qua vị trí cuối đã xong. Lặp cho đến khi không còn đổi nào.

Selection — tìm nhỏ nhất, đặt vào đầu: Lướt qua toàn bộ bài, chọn ra quân nhỏ nhất, đổi với quân ở vị trí đầu. Bây giờ vị trí đầu đã xong. Lặp lại với phần còn lại, mỗi lần chọn nhỏ nhất trong phần chưa xử lý.

Insertion — cầm từng quân, đẩy vào chỗ đúng: Cầm quân thứ 2, đẩy vào vị trí đúng trong 2 quân đầu. Cầm quân thứ 3, đẩy vào chỗ đúng trong 3 quân đầu. Phần bên trái tay luôn đã sorted — giống khi bạn cầm bài và xếp từng lá vào đúng vị trí.

2. Bubble sort

BubbleSort(A):
    n <- A.length
    for i <- 0 đến n-2:
        swapped <- false
        for j <- 0 đến n-2-i:
            if A[j] > A[j+1]:
                swap A[j] và A[j+1]
                swapped <- true
        if not swapped: break     -- đã sorted, thoát sớm

Time: O(n²) worst/average, O(n) best Space: O(1)

Dòng if not swapped: break là optimization quan trọng: nếu một pass không có swap nào, array đã sorted và thuật toán dừng sớm.

graph LR
    A["[5, 3, 1, 4, 2]<br/>ban đầu"]
    B["[3, 1, 4, 2, 5]<br/>sau pass 1: 5 nổi lên cuối"]
    C["[1, 3, 2, 4, 5]<br/>sau pass 2: 4 đúng vị trí"]
    D["[1, 2, 3, 4, 5]<br/>sau pass 3: xong"]

    A --> B --> C --> D

Phân tích:

• Best case O(n): input đã sorted → pass đầu không swap → break ngay. Một lần quét duy nhất.
• Worst case O(n²): input sorted ngược → mỗi element phải bubble qua toàn bộ array.
• Stable: khi bằng nhau (==) không swap, giữ thứ tự gốc.
• Adaptive: có early exit, nhưng thực tế vẫn chậm hơn Insertion sort trên nearly-sorted data.

Production rating: hiếm có lý do dùng. Trong code review, cần replace ngay bằng built-in sort.

3. Selection sort

SelectionSort(A):
    n <- A.length
    for i <- 0 đến n-2:
        minIdx <- i
        for j <- i+1 đến n-1:
            if A[j] < A[minIdx]: minIdx <- j
        swap A[i] và A[minIdx]    -- đặt phần tử nhỏ nhất vào vị trí i

Time: O(n²) mọi trường hợp Space: O(1)

Phân tích:

• Luôn O(n²): không adaptive. Dù input đã sorted hay sorted ngược, vòng lặp trong vẫn quét toàn bộ phần còn lại để tìm min. Không có early exit.
• Stable: không. Swap A[i] với A[minIdx] có thể nhảy qua element bằng nhau nằm giữa — phá vỡ thứ tự tương đối.
• Ưu điểm duy nhất — ít swap: đúng n-1 lần swap, không bao giờ nhiều hơn. Khi swap đắt (object lớn, disk write), Selection sort có lợi thế.

Production rating: dùng khi swap đắt hơn compare. Hiếm trong thực tế hiện đại. Phù hợp hơn với một số ngữ cảnh embedded hoặc sorting danh sách có large payload.

4. Insertion sort — adaptive winner

InsertionSort(A):
    for i <- 1 đến A.length-1:
        key <- A[i]
        j <- i - 1
        while j >= 0 và A[j] > key:   -- j >= 0 phải đứng TRƯỚC để tránh lỗi
            A[j+1] <- A[j]            -- shift phải, không swap
            j <- j - 1
        A[j+1] <- key

Time: O(n²) worst, O(n) best, O(n+d) với d = số inversion Space: O(1)

Cơ chế quan trọng: Insertion sort shift element sang phải thay vì swap từng cặp. Mỗi iteration chỉ ghi một lần vào A[j+1] = key ở cuối — tiết kiệm hơn Bubble sort swap từng cặp.

Phân tích:

• Best case O(n): input đã sorted → điều kiện A[j] > key false ngay → chỉ có vòng for ngoài O(n).
• Worst case O(n²): input sorted ngược → mỗi key phải shift qua toàn bộ phần đã sorted.
• Adaptive — O(n + d): với d = số inversion (cặp (i,j) mà i nhỏ hơn j nhưng A[i] lớn hơn A[j]). Nearly-sorted array có d nhỏ → gần O(n). Đây là lợi thế chính.
• Stable: điều kiện A[j] > key (strict greater) — khi bằng nhau không shift, giữ thứ tự gốc.
• Online: có thể sort data đến từng phần — nhận element mới, chèn vào vị trí đúng trong phần đã sorted.

5. Bảng so sánh và benchmark thực tế

Benchmark thực tế trên mảng 10.000 phần tử ngẫu nhiên (JMH warm-up 5 iteration):

Insertion thắng Bubble và Selection khoảng 2x nhờ shift thay vì swap. Nhưng built-in sort nhanh hơn 50-100x.

Benchmark với n = 16 phần tử (subarray nhỏ):

Với n nhỏ, built-in sort chậm hơn Insertion sort vì overhead của recursion, pivot selection, và function call. Insertion sort chạy thẳng, không recursion, không allocation — thắng hoàn toàn ở n nhỏ.

Đây là lý do TimSort gọi Insertion sort cho subarray dưới 32 phần tử. Constants matter ở n nhỏ.

6. Pitfall tổng hợp

Pitfall 1 — Bubble sort trong code production

Bubble sort vẫn xuất hiện trong code production vì developer nhớ cú pháp từ năm nhất rồi copy paste. Kết quả: mảng 10.000 phần tử mất 120ms thay vì 1.2ms — chênh lệch 100x.

-- BUG: O(n²) -- không dùng trong production
for i <- 0 đến n-2:
    for j <- 0 đến n-2-i:
        if A[j] > A[j+1]: swap A[j] và A[j+1]

-- ĐÚNG: dùng built-in sort O(n log n)
-- Arrays.sort(arr) hoặc Collections.sort(list)

Time: O(n²) — BUG vs O(n log n) — ĐÚNG

Rule: nếu bạn thấy Bubble sort trong code review, yêu cầu replace ngay. Không có use case production nào biện minh cho Bubble sort khi built-in sort đã sẵn có.

Pitfall 2 — Selection sort không stable, nhưng dev assume mọi sort là stable

Selection sort không stable — swap A[i] với A[minIdx] có thể nhảy qua element bằng nhau.

-- Ví dụ: sắp nhân viên [Alice:50k, Bob:50k, Carol:40k]
-- Bước 1 sort theo lương: đúng thứ tự Carol < Alice = Bob
-- Bước 2 sort theo phòng ban bằng Selection sort:
--   swap có thể đổi chỗ Alice và Bob (hai người cùng 50k)
--   => thứ tự lương trong cùng phòng ban: không xác định ✗

-- ĐÚNG: dùng stable sort ở bước 2 (Insertion sort, Merge sort, TimSort)
--   => trong cùng phòng ban, thứ tự lương từ bước 1 được bảo toàn ✓

Rule: trước khi dùng bất kỳ sort nào trong multi-key scenario, verify stability.

Pitfall 3 — Thứ tự điều kiện trong Insertion sort while loop

-- BUG: ArrayIndexOutOfBoundsException khi j = -1
while A[j] > key và j >= 0:
    -- A[j] được evaluate khi j = -1 -> lỗi index

-- ĐÚNG: kiểm tra j >= 0 TRƯỚC (short-circuit)
while j >= 0 và A[j] > key:
    A[j+1] <- A[j]
    j <- j - 1

Đảo ngược thứ tự thì A[j] được evaluate trước — với j = -1 gây lỗi index out of bounds. Lỗi này hay xuất hiện trong coding interview và code được viết "từ trí nhớ" mà không chạy test.

7. Insertion sort variants

Binary Insertion sort: thay vì tìm vị trí chèn bằng linear scan O(n), dùng binary search O(log n). Tổng số phép compare giảm xuống O(n log n). Nhưng tổng thời gian vẫn O(n²) vì shift phần tử vẫn tốn O(n) per iteration — shift dominates, không phải compare.

BinaryInsertionSort(A):
    for i <- 1 đến A.length-1:
        key <- A[i]
        -- tìm vị trí chèn bằng binary search trong A[0..i-1]
        pos <- binarySearch(A, 0, i-1, key)
        -- shift A[pos..i-1] sang phải 1 vị trí
        for j <- i-1 xuống pos:
            A[j+1] <- A[j]
        A[pos] <- key

Time: O(n²) (shift vẫn O(n²)) Space: O(1)

Variant này hữu ích cho linked list nơi insert O(1) — binary search + O(1) insert = O(n log n) thực sự. Với array, shift là bottleneck nên lợi ích hạn chế.

Shell sort: Insertion sort + gap sequence. Sort các phần tử cách nhau gap bước, sau đó giảm gap dần đến 1. Worst case O(n^1.5) đến O(n log² n) tùy gap sequence — tốt hơn O(n²) thuần túy. Hiếm dùng trong production hiện đại nhưng có giá trị học thuật.

8. Vì sao TimSort vẫn dùng Insertion sort

Real-world data thường có structure — không random hoàn toàn. Log file sorted theo timestamp, transaction ID tăng dần, event stream có thứ tự tự nhiên. TimSort khai thác điều này qua 3 bước:

TimSort (rút gọn):
    runs <- []
    i <- 0
    while i < A.length:
        run <- detectRun(A, i)    -- tìm đoạn đã sorted (tăng hoặc giảm)
        if run.length < minRunLength:
            extendByInsertionSort(A, run, minRunLength)  -- Insertion sort cho run ngắn
        runs.push(run)
        i <- run.end
    mergeRunsOptimally(runs)      -- merge theo stack-based strategy

Time: O(n) cho input đã sorted, O(n log n) worst Space: O(n)

Insertion sort phù hợp ở bước extend vì:

• Run ngắn (32-64 phần tử) → n nhỏ → Insertion sort thắng về constant factor.
• Run thường "gần sorted" → d (số inversion) nhỏ → Insertion sort gần O(n).
• Không cần recursion hay allocation → overhead thấp nhất có thể.

Cross-link: Module 2 lesson 09 sẽ là case study sâu về TimSort internals — galloping mode, merge policy, run detection chi tiết.

9. Ứng dụng thực tế

TimSort — threshold 32-47: TimSort gọi Insertion sort cho subarray ngắn hơn minRunLength. Với mảng số nguyên nguyên thủy, JDK dùng threshold 47 — xác định qua benchmarking thực nghiệm, không phải con số lý thuyết.

-- Từ DualPivotQuicksort (rút gọn):
if subarray.length < INSERTION_SORT_THRESHOLD:
    insertionSort(subarray)  -- nhanh hơn Quick sort ở đây
    return
-- ... tiếp tục dual-pivot partition

Online algorithms — sort data streaming: Insertion sort có thể sort data khi nó đến từng phần — nhận event mới, chèn vào vị trí đúng trong phần đã sorted. Bubble sort và Selection sort cần full data trước khi bắt đầu.

Use case thực tế: buffer incoming trade orders và maintain sorted order by price/time priority. Với số lượng orders trong buffer thấp (thường dưới 100), Insertion sort O(n) cho insert vào sorted array thắng về latency.

Embedded / memory-constrained: Insertion sort code rất ngắn, không dùng recursion stack, in-place O(1). Phù hợp microcontroller hoặc kernel-level sort nơi binary size và stack depth bị giới hạn nghiêm ngặt. Linux kernel dùng Insertion sort cho một số small list sort.

10. Deep Dive

11. Tóm tắt

• Bubble sort O(n²): stable, có early exit khi sorted, nhưng thực tế chậm hơn Insertion. Dùng trong production là dấu hiệu cần refactor ngay.
• Selection sort O(n²): không adaptive, không stable, nhưng chỉ n-1 lần swap. Hữu ích khi swap đắt hơn compare.
• Insertion sort O(n²): stable, adaptive O(n+d), online — ba đặc tính khiến nó vẫn xuất hiện trong production library.
• Constants matter ở n nhỏ: Insertion sort thắng built-in sort khi n dưới khoảng 47 vì không có recursion overhead.
• TimSort dùng Insertion sort để extend run ngắn — subarray nhỏ + gần sorted = Insertion sort gần O(n).
• Thứ tự điều kiện while j >= 0 và A[j] > key — j >= 0 phải đứng trước để tránh lỗi index out of bounds.
• Selection sort không stable — không dùng cho multi-key sort mà giả định stable behavior.

12. Tự kiểm tra

Bài tiếp theo: Merge sort — divide and conquer, stable O(n log n)