Quick Sort — Sắp xếp nhanh

Hàm qsort() trong C standard library, std::sort() trong C++ STL (introsort — hybrid Quick Sort + Heap Sort), Arrays.sort() cho primitive types trong Java — tất cả đều xây trên nền Quick Sort. Đây không phải thuật toán "học cho biết" mà là thuật toán đang chạy trên hàng tỷ thiết bị mỗi ngày.

Quick Sort và Merge Sort đều dùng chiến thuật Divide and Conquer, nhưng khác nhau ở điểm mấu chốt: Merge Sort làm việc nặng ở bước gộp (merge), còn Quick Sort dồn toàn bộ công sức vào bước chia (partition). Sau khi partition xong, mỗi phần tử pivot đã nằm đúng vị trí cuối cùng — không cần merge gì thêm.

Hiểu sâu thao tác partition không chỉ giúp bạn nắm Quick Sort, mà còn mở khóa hàng loạt bài toán phỏng vấn: tìm phần tử lớn thứ k (Quick Select), Dutch National Flag problem, hay partitioning trong xử lý database query.

Bức tranh tư duy

Hình dung một nhà quản lý phân xưởng cần xếp 100 công nhân theo chiều cao. Thay vì so sánh từng cặp, anh ta chọn một người làm mốc (pivot) rồi hô: "Ai thấp hơn người này đứng bên trái, ai cao hơn đứng bên phải." Sau một lượt, người-mốc đã đứng đúng vị trí.

Tiếp theo, anh ta cử hai quản lý phụ — mỗi người lặp lại quy trình cho nhóm bên trái và nhóm bên phải. Cứ thế đệ quy cho đến khi mỗi nhóm chỉ còn 1 người.

text

Mảng ban đầu:    [8, 3, 1, 7, 0, 10, 2]     pivot = 7

Partition:
  Trái (< 7):    [3, 1, 0, 2]
  Pivot:          [7]           ← đã đúng vị trí!
  Phải (≥ 7):    [8, 10]

Đệ quy trái:     [3, 1, 0, 2]  pivot = 1  →  [0] [1] [3, 2]
Đệ quy phải:     [8, 10]       pivot = 8  →  [] [8] [10]
...
Kết quả:          [0, 1, 2, 3, 7, 8, 10]

Điểm then chốt: sau mỗi lần partition, pivot luôn nằm đúng vị trí cuối cùng. Không ai cần dời pivot nữa. Đây là lý do Quick Sort không cần bước merge tốn kém như Merge Sort.

📌 Khi nào analogy bị phá vỡ

Trong thực tế, "nhà quản lý" chọn mốc ngẫu nhiên có thể gặp xui — chọn trúng người cao nhất hoặc thấp nhất, khiến một bên trống rỗng. Đó chính là worst case O(n²) mà ta sẽ phân tích ở phần Under the Hood.

Cốt lõi kỹ thuật

Partition — trái tim của Quick Sort

Partition nhận một mảng con arr[low..high], chọn một phần tử làm pivot, rồi sắp xếp lại sao cho:

Mọi phần tử < pivot nằm bên trái
Mọi phần tử ≥ pivot nằm bên phải
Pivot nằm đúng vị trí cuối cùng

Có hai sơ đồ partition phổ biến: Lomuto và Hoare.

Lomuto Partition Scheme

Lomuto chọn phần tử cuối arr[high] làm pivot. Dùng một con trỏ i đánh dấu ranh giới vùng "nhỏ hơn pivot". Quét j từ low đến high - 1: gặp phần tử nhỏ hơn pivot thì swap vào vùng trái.

text

arr = [2, 8, 7, 1, 3, 5, 6, 4]    pivot = 4, i = -1

j=0: arr[0]=2 < 4 → i=0, swap(arr[0], arr[0]) → [2, 8, 7, 1, 3, 5, 6, 4]
j=1: arr[1]=8 ≥ 4 → skip
j=2: arr[2]=7 ≥ 4 → skip
j=3: arr[3]=1 < 4 → i=1, swap(arr[1], arr[3]) → [2, 1, 7, 8, 3, 5, 6, 4]
j=4: arr[4]=3 < 4 → i=2, swap(arr[2], arr[4]) → [2, 1, 3, 8, 7, 5, 6, 4]
j=5: arr[5]=5 ≥ 4 → skip
j=6: arr[6]=6 ≥ 4 → skip

Cuối: swap(arr[i+1], arr[high]) → swap(arr[3], arr[7])
Kết quả: [2, 1, 3, 4, 7, 5, 6, 8]    pivot 4 ở index 3 ✓

C++PythonJavaGo

cpp

#include <algorithm>

int lomutoPartition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSortLomuto(int arr[], int low, int high) {
    if (low < high) {
        int pi = lomutoPartition(arr, low, high);
        quickSortLomuto(arr, low, pi - 1);
        quickSortLomuto(arr, pi + 1, high);
    }
}

python

def lomuto_partition(arr: list[int], low: int, high: int) -> int:
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


def quick_sort_lomuto(arr: list[int], low: int, high: int) -> None:
    if low < high:
        pi = lomuto_partition(arr, low, high)
        quick_sort_lomuto(arr, low, pi - 1)
        quick_sort_lomuto(arr, pi + 1, high)

java

public class QuickSort {

    static int lomutoPartition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    static void quickSortLomuto(int[] arr, int low, int high) {
        if (low < high) {
            int pi = lomutoPartition(arr, low, high);
            quickSortLomuto(arr, low, pi - 1);
            quickSortLomuto(arr, pi + 1, high);
        }
    }
}

package sorting

func lomutoPartition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low - 1

    for j := low; j < high; j++ {
        if arr[j] < pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

func QuickSortLomuto(arr []int, low, high int) {
    if low < high {
        pi := lomutoPartition(arr, low, high)
        QuickSortLomuto(arr, low, pi-1)
        QuickSortLomuto(arr, pi+1, high)
    }
}

Hoare Partition Scheme

Hoare — sơ đồ gốc của C.A.R. Hoare (1961) — dùng hai con trỏ chạy ngược chiều từ hai đầu mảng. Con trỏ trái tìm phần tử ≥ pivot, con trỏ phải tìm phần tử ≤ pivot, rồi swap. Lặp đến khi hai con trỏ giao nhau.

Hoare thực hiện ít swap hơn Lomuto trung bình ~3 lần, đặc biệt hiệu quả khi mảng có nhiều phần tử trùng lặp.

C++PythonJavaGo

cpp

#include <algorithm>

int hoarePartition(int arr[], int low, int high) {
    int pivot = arr[low + (high - low) / 2];
    int i = low - 1;
    int j = high + 1;

    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);

        if (i >= j) return j;
        std::swap(arr[i], arr[j]);
    }
}

void quickSortHoare(int arr[], int low, int high) {
    if (low < high) {
        int p = hoarePartition(arr, low, high);
        quickSortHoare(arr, low, p);       // chú ý: p, không phải p-1
        quickSortHoare(arr, p + 1, high);
    }
}

python

def hoare_partition(arr: list[int], low: int, high: int) -> int:
    pivot = arr[low + (high - low) // 2]
    i = low - 1
    j = high + 1

    while True:
        i += 1
        while arr[i] < pivot:
            i += 1

        j -= 1
        while arr[j] > pivot:
            j -= 1

        if i >= j:
            return j
        arr[i], arr[j] = arr[j], arr[i]


def quick_sort_hoare(arr: list[int], low: int, high: int) -> None:
    if low < high:
        p = hoare_partition(arr, low, high)
        quick_sort_hoare(arr, low, p)       # chú ý: p, không phải p-1
        quick_sort_hoare(arr, p + 1, high)

java

public class QuickSortHoare {

    static int hoarePartition(int[] arr, int low, int high) {
        int pivot = arr[low + (high - low) / 2];
        int i = low - 1;
        int j = high + 1;

        while (true) {
            do { i++; } while (arr[i] < pivot);
            do { j--; } while (arr[j] > pivot);

            if (i >= j) return j;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    static void quickSortHoare(int[] arr, int low, int high) {
        if (low < high) {
            int p = hoarePartition(arr, low, high);
            quickSortHoare(arr, low, p);
            quickSortHoare(arr, p + 1, high);
        }
    }
}

package sorting

func hoarePartition(arr []int, low, high int) int {
    pivot := arr[low+(high-low)/2]
    i := low - 1
    j := high + 1

    for {
        for i++; arr[i] < pivot; i++ {}
        for j--; arr[j] > pivot; j-- {}

        if i >= j {
            return j
        }
        arr[i], arr[j] = arr[j], arr[i]
    }
}

func QuickSortHoare(arr []int, low, high int) {
    if low < high {
        p := hoarePartition(arr, low, high)
        QuickSortHoare(arr, low, p)
        QuickSortHoare(arr, p+1, high)
    }
}

⚠️ Khác biệt quan trọng giữa Lomuto và Hoare

Với Lomuto, sau partition pivot nằm tại arr[pi] → đệ quy trên [low, pi-1] và [pi+1, high]. Với Hoare, giá trị trả về p không phải vị trí cuối cùng của pivot → đệ quy trên [low, p] và [p+1, high]. Nhầm chỗ này là bug cực kỳ khó tìm.

Chiến lược chọn Pivot

Chiến lược	Cách chọn	Ưu điểm	Nhược điểm
First/Last	`arr[low]` hoặc `arr[high]`	Đơn giản	O(n²) trên mảng đã sắp xếp
Random	`arr[random(low, high)]`	Tránh worst case gần như tuyệt đối	Cần random number generator
Median-of-three	Trung vị của `arr[low]`, `arr[mid]`, `arr[high]`	Balance tốt, deterministic	Phức tạp hơn một chút
Ninther	Median-of-three medians	Gần optimal	Overhead không đáng cho mảng nhỏ

Trong production, median-of-three là lựa chọn phổ biến nhất (C++ STL dùng nó trong introsort).

3-Way Partition — Dutch National Flag

Khi mảng có nhiều phần tử trùng lặp, partition 2 chiều (< và ≥) tạo ra mảng con lớn chứa toàn giá trị bằng pivot — lãng phí. 3-way partition chia thành ba vùng: < pivot, == pivot, > pivot.

C++PythonJavaGo

cpp

#include <algorithm>
#include <utility>

// Trả về [lt, gt]: arr[low..lt-1] < pivot, arr[lt..gt] == pivot, arr[gt+1..high] > pivot
std::pair<int, int> threeWayPartition(int arr[], int low, int high) {
    int pivot = arr[low + (high - low) / 2];
    int lt = low, i = low, gt = high;

    while (i <= gt) {
        if (arr[i] < pivot) {
            std::swap(arr[lt], arr[i]);
            lt++;
            i++;
        } else if (arr[i] > pivot) {
            std::swap(arr[i], arr[gt]);
            gt--;
        } else {
            i++;
        }
    }
    return {lt, gt};
}

void quickSort3Way(int arr[], int low, int high) {
    if (low >= high) return;
    auto [lt, gt] = threeWayPartition(arr, low, high);
    quickSort3Way(arr, low, lt - 1);
    quickSort3Way(arr, gt + 1, high);
}

python

def three_way_partition(arr: list[int], low: int, high: int) -> tuple[int, int]:
    """Dutch National Flag partition.
    Trả về (lt, gt): arr[low..lt-1] < pivot, arr[lt..gt] == pivot, arr[gt+1..high] > pivot
    """
    pivot = arr[low + (high - low) // 2]
    lt, i, gt = low, low, high

    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1

    return lt, gt


def quick_sort_3way(arr: list[int], low: int, high: int) -> None:
    if low >= high:
        return
    lt, gt = three_way_partition(arr, low, high)
    quick_sort_3way(arr, low, lt - 1)
    quick_sort_3way(arr, gt + 1, high)

java

public class QuickSort3Way {

    static void quickSort3Way(int[] arr, int low, int high) {
        if (low >= high) return;

        int pivot = arr[low + (high - low) / 2];
        int lt = low, i = low, gt = high;

        while (i <= gt) {
            if (arr[i] < pivot) {
                int temp = arr[lt]; arr[lt] = arr[i]; arr[i] = temp;
                lt++;
                i++;
            } else if (arr[i] > pivot) {
                int temp = arr[i]; arr[i] = arr[gt]; arr[gt] = temp;
                gt--;
            } else {
                i++;
            }
        }
        quickSort3Way(arr, low, lt - 1);
        quickSort3Way(arr, gt + 1, high);
    }
}

package sorting

func QuickSort3Way(arr []int, low, high int) {
    if low >= high {
        return
    }

    pivot := arr[low+(high-low)/2]
    lt, i, gt := low, low, high

    for i <= gt {
        if arr[i] < pivot {
            arr[lt], arr[i] = arr[i], arr[lt]
            lt++
            i++
        } else if arr[i] > pivot {
            arr[i], arr[gt] = arr[gt], arr[i]
            gt--
        } else {
            i++
        }
    }
    QuickSort3Way(arr, low, lt-1)
    QuickSort3Way(arr, gt+1, high)
}

Thực chiến

Tình huống 1: Quick Select — tìm phần tử lớn thứ k trong O(n)

Bối cảnh: Hệ thống monitoring cần tìm percentile thứ 99 của latency từ mảng 10 triệu request — không cần sort toàn bộ, chỉ cần phần tử tại vị trí thứ k.

Mục tiêu: Tìm phần tử lớn thứ k trong thời gian trung bình O(n), thay vì O(n log n) khi sort toàn bộ.

Quick Select tái sử dụng thao tác partition: sau mỗi lần partition, pivot nằm đúng vị trí. Nếu vị trí đó là k — xong. Nếu không, chỉ đệ quy vào một nửa chứa vị trí k.

C++PythonJavaGo

cpp

#include <algorithm>
#include <cstdlib>

int quickSelect(int arr[], int low, int high, int k) {
    if (low == high) return arr[low];

    // Random pivot để tránh worst case
    int pivotIdx = low + rand() % (high - low + 1);
    std::swap(arr[pivotIdx], arr[high]);

    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    int pi = i + 1;

    if (pi == k)      return arr[pi];
    else if (pi < k)  return quickSelect(arr, pi + 1, high, k);
    else               return quickSelect(arr, low, pi - 1, k);
}

python

import random

def quick_select(arr: list[int], low: int, high: int, k: int) -> int:
    """Tìm phần tử tại vị trí k (0-indexed) nếu mảng được sort."""
    if low == high:
        return arr[low]

    # Random pivot để tránh worst case
    pivot_idx = random.randint(low, high)
    arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]

    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    pi = i + 1

    if pi == k:
        return arr[pi]
    elif pi < k:
        return quick_select(arr, pi + 1, high, k)
    else:
        return quick_select(arr, low, pi - 1, k)

java

import java.util.Random;

public class QuickSelect {
    private static final Random rng = new Random();

    public static int quickSelect(int[] arr, int low, int high, int k) {
        if (low == high) return arr[low];

        int pivotIdx = low + rng.nextInt(high - low + 1);
        int temp = arr[pivotIdx]; arr[pivotIdx] = arr[high]; arr[high] = temp;

        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
            }
        }
        temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp;
        int pi = i + 1;

        if (pi == k)      return arr[pi];
        else if (pi < k)  return quickSelect(arr, pi + 1, high, k);
        else               return quickSelect(arr, low, pi - 1, k);
    }
}

package sorting

import "math/rand"

func QuickSelect(arr []int, low, high, k int) int {
    if low == high {
        return arr[low]
    }

    pivotIdx := low + rand.Intn(high-low+1)
    arr[pivotIdx], arr[high] = arr[high], arr[pivotIdx]

    pivot := arr[high]
    i := low - 1
    for j := low; j < high; j++ {
        if arr[j] <= pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1]
    pi := i + 1

    if pi == k {
        return arr[pi]
    } else if pi < k {
        return QuickSelect(arr, pi+1, high, k)
    }
    return QuickSelect(arr, low, pi-1, k)
}

Phân tích:

Trung bình O(n): mỗi lần partition loại bỏ ~50% phần tử → n + n/2 + n/4 + ... ≈ 2n
Worst case O(n²) nhưng random pivot khiến xác suất này cực kỳ thấp
Dùng trong std::nth_element (C++ STL) và nhiều thư viện statistics

Tình huống 2: Introsort — Quick Sort trong thực tế production

Bối cảnh: C++ STL std::sort() không dùng Quick Sort thuần mà dùng introsort — hybrid giữa Quick Sort, Heap Sort, và Insertion Sort.

Cơ chế:

Bắt đầu bằng Quick Sort với median-of-three pivot
Nếu recursion depth vượt 2 × log₂(n) → chuyển sang Heap Sort (đảm bảo O(n log n) worst case)
Khi mảng con ≤ 16 phần tử → chuyển sang Insertion Sort (nhanh hơn cho mảng nhỏ do overhead thấp)

Đây là lý do std::sort() đảm bảo O(n log n) worst case mà vẫn nhanh như Quick Sort trên average case.

Sai lầm điển hình

❌ Sai lầm 1: Chọn pivot cố định trên mảng đã sắp xếp

Vấn đề: Luôn chọn phần tử đầu hoặc cuối làm pivot.

python

# SAI: pivot luôn là phần tử cuối
def partition(arr, low, high):
    pivot = arr[high]  # Nếu mảng đã sorted → pivot luôn là max → O(n²)
    ...

Tại sao sai: Trên mảng đã sắp xếp (hoặc gần sắp xếp — rất phổ biến trong production khi data đến từ database), mỗi lần partition chỉ loại được 1 phần tử → n lần partition × n comparisons = O(n²). Với n = 1 triệu, đó là 10¹² operations thay vì ~20 triệu.

python

# ĐÚNG: random pivot hoặc median-of-three
import random

def partition(arr, low, high):
    pivot_idx = random.randint(low, high)
    arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
    pivot = arr[high]
    ...

❌ Sai lầm 2: Stack overflow với đệ quy sâu

Vấn đề: Quick Sort đệ quy trên cả hai nhánh mà không tối ưu tail call.

cpp

// SAI: đệ quy cả hai nhánh — stack depth có thể tới O(n)
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);  // nhánh này có thể tail-call optimize
    }
}

Tại sao sai: Với mảng 1 triệu phần tử và worst case, stack depth là 1 triệu frame. Default stack size (thường 1-8 MB) sẽ tràn. Production systems crash không báo trước.

cpp

// ĐÚNG: tail-call optimization — luôn đệ quy nhánh nhỏ, loop nhánh lớn
void quickSort(int arr[], int low, int high) {
    while (low < high) {
        int pi = partition(arr, low, high);
        if (pi - low < high - pi) {
            quickSort(arr, low, pi - 1);  // đệ quy nhánh nhỏ
            low = pi + 1;                 // loop nhánh lớn
        } else {
            quickSort(arr, pi + 1, high);
            high = pi - 1;
        }
    }
}

Kỹ thuật này đảm bảo stack depth luôn O(log n), bất kể input.

❌ Sai lầm 3: Không xử lý mảng toàn phần tử giống nhau

Vấn đề: Dùng partition 2 chiều (Lomuto/Hoare cơ bản) trên mảng có nhiều duplicates.

python

# SAI: mảng [5, 5, 5, 5, 5] → mỗi partition chỉ loại 1 phần tử → O(n²)
arr = [5] * 1000000
quick_sort_lomuto(arr, 0, len(arr) - 1)  # Cực chậm!

Tại sao sai: Với Lomuto, tất cả phần tử bằng pivot dồn về một bên → phân chia lệch tối đa. Trong thực tế, data thường có nhiều giá trị trùng (ví dụ: status codes, age groups, ratings).

python

# ĐÚNG: dùng 3-way partition (Dutch National Flag)
quick_sort_3way(arr, 0, len(arr) - 1)  # O(n) cho mảng toàn duplicates!

❌ Sai lầm 4: Nhầm lẫn đệ quy giữa Lomuto và Hoare

Vấn đề: Dùng cách gọi đệ quy của Lomuto cho Hoare partition.

cpp

// SAI: dùng đệ quy kiểu Lomuto (pi-1, pi+1) với Hoare partition
int p = hoarePartition(arr, low, high);
quickSort(arr, low, p - 1);   // BUG: bỏ sót phần tử tại p
quickSort(arr, p + 1, high);

Tại sao sai: Hoare partition trả về vị trí phân chia, không phải vị trí cuối cùng của pivot. Pivot có thể nằm ở bất kỳ đâu trong nửa trái. Viết p - 1 thay vì p sẽ bỏ sót phần tử → mảng không được sort đúng. Bug này pass hầu hết test cases nhỏ nhưng fail trên input lớn — rất khó debug.

cpp

// ĐÚNG: đệ quy Hoare — nửa trái bao gồm p
int p = hoarePartition(arr, low, high);
quickSort(arr, low, p);        // bao gồm p
quickSort(arr, p + 1, high);

❌ Sai lầm 5: Không switch sang Insertion Sort cho mảng nhỏ

Vấn đề: Đệ quy Quick Sort đến tận base case low >= high.

Tại sao sai: Quick Sort có overhead cho mỗi lần gọi hàm (stack frame, partition setup). Với mảng ≤ 10-20 phần tử, Insertion Sort nhanh hơn đáng kể nhờ hằng số nhỏ và cache locality tốt. Đây là lý do mọi production implementation đều có ngưỡng cutoff.

cpp

// ĐÚNG: cutoff sang Insertion Sort
void quickSort(int arr[], int low, int high) {
    if (high - low < 16) {
        insertionSort(arr, low, high);
        return;
    }
    int pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
}

Under the Hood

Hiệu năng

Trường hợp	Time	Space	Điều kiện
Best case	O(n log n)	O(log n)	Pivot luôn chia đều mảng
Average case	O(n log n)	O(log n)	Random pivot / dữ liệu ngẫu nhiên
Worst case	O(n²)	O(n)	Pivot luôn là min hoặc max
3-way (duplicates)	O(n)	O(log n)	Toàn phần tử giống nhau

Tại sao worst case gần như không xảy ra với random pivot

Xác suất chọn pivot rơi vào 25%-75% vị trí là 50% cho mỗi lần partition. Để xảy ra worst case, ta cần chọn sai mọi lần — xác suất (1/2)ⁿ. Với n = 1000, xác suất worst case là ~10⁻³⁰⁰ — nhỏ hơn xác suất bạn trúng sổ xố 40 lần liên tiếp.

Tại sao Quick Sort thắng Merge Sort trong thực tế

Yếu tố	Quick Sort	Merge Sort
Space	O(log n) in-place	O(n) cần mảng tạm
Cache	Truy cập tuần tự, cache-friendly	Merge cần nhảy giữa hai mảng
Hằng số	Nhỏ hơn ~2-3×	Lớn hơn do copy vào mảng tạm
Stability	❌ Không stable	✅ Stable
Worst case	O(n²)	O(n log n) đảm bảo

Quick Sort thắng nhờ locality of reference: CPU cache line (thường 64 bytes = 16 integers) được tận dụng tối đa vì partition quét mảng tuần tự. Merge Sort phải đọc từ hai mảng khác nhau, gây cache miss.

Introsort: Quick Sort không sợ worst case

Introsort (introspective sort) kết hợp ba thuật toán:

Quick Sort cho average case nhanh
Heap Sort fallback khi recursion depth vượt 2 × log₂(n) → đảm bảo O(n log n)
Insertion Sort cho mảng con nhỏ (≤ 16 phần tử)

Đây là thuật toán mà std::sort() trong C++ STL thực sự dùng. Java dùng dual-pivot Quick Sort cho primitive types (hai pivot chia mảng thành 3 phần).

Trade-offs

Khi nào NÊN dùng Quick Sort: Sorting in-place khi memory là ràng buộc, primitive types không cần stability, general-purpose sorting.

Khi nào KHÔNG NÊN dùng: Cần stable sort (dùng Merge Sort/Timsort), dữ liệu gần sorted (Timsort tối ưu hơn), linked list (Merge Sort tự nhiên hơn), real-time systems cần worst case guarantee (dùng Heap Sort).

Checklist ghi nhớ

✅ Checklist triển khai

Partition fundamentals

[ ] Phân biệt được Lomuto (1 con trỏ, pivot cuối) và Hoare (2 con trỏ ngược chiều)
[ ] Hiểu tại sao đệ quy Lomuto dùng [low, pi-1] + [pi+1, high] còn Hoare dùng [low, p] + [p+1, high]
[ ] Cài đặt được 3-way partition (Dutch National Flag) cho mảng nhiều duplicates

Pivot selection

[ ] Mặc định dùng random pivot hoặc median-of-three — không bao giờ dùng pivot cố định
[ ] Hiểu tại sao pivot cố định gây O(n²) trên sorted input
[ ] Biết khi nào dùng ninther (median-of-three medians) cho mảng cực lớn

Tối ưu production

[ ] Áp dụng tail-call optimization: đệ quy nhánh nhỏ, loop nhánh lớn → stack O(log n)
[ ] Cutoff sang Insertion Sort khi mảng con ≤ 16 phần tử
[ ] Hiểu introsort: Quick Sort + Heap Sort fallback khi depth vượt 2×log₂(n)

Ứng dụng mở rộng

[ ] Cài đặt được Quick Select để tìm phần tử thứ k trong O(n) trung bình
[ ] Biết std::nth_element (C++), numpy.partition (Python) dựa trên Quick Select
[ ] Hiểu partition là nền tảng cho nhiều bài toán: Dutch National Flag, 2-way merge, database query processing

Bài tập luyện tập

Bài 1: Sort Colors (Dutch National Flag) — Foundation

Đề bài: Cho mảng chỉ chứa 3 giá trị 0, 1, 2 (đại diện đỏ, trắng, xanh). Sắp xếp mảng tại chỗ chỉ trong một lần duyệt, không dùng counting sort.

Input: [2, 0, 2, 1, 1, 0]Output: [0, 0, 1, 1, 2, 2]

Gợi ý: Đây chính là 3-way partition với pivot = 1.

🧠 Quiz

Quick Sort partition trả về gì?

[ ] A. Mảng đã được sắp xếp hoàn toàn
[x] B. Vị trí cuối cùng của pivot, với tất cả phần tử nhỏ hơn ở bên trái và lớn hơn ở bên phải
[ ] C. Hai mảng con đã sắp xếp riêng biệt
[ ] D. Phần tử lớn nhất của mảng Giải thích: Partition chỉ đảm bảo pivot nằm đúng vị trí cuối cùng và phân chia mảng thành hai phần (nhỏ hơn / lớn hơn pivot). Hai phần này chưa được sắp xếp — đệ quy sẽ xử lý tiếp.

💡 Gợi ý

Dùng 3 con trỏ: low (ranh giới vùng 0), mid (đang xét), high (ranh giới vùng 2)
arr[mid] == 0 → swap với arr[low], tăng cả hai
arr[mid] == 2 → swap với arr[high], chỉ giảm high
arr[mid] == 1 → chỉ tăng mid

✅ Lời giải

python

def sort_colors(nums: list[int]) -> None:
    low, mid, high = 0, 0, len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 2:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
        else:
            mid += 1

Phân tích: Time O(n) — mỗi phần tử được xét tối đa 2 lần. Space O(1). Chính xác là 3-way partition của Quick Sort với pivot = 1.

Bài 2: Kth Largest Element — Intermediate

Đề bài: Cho mảng nums và số nguyên k, tìm phần tử lớn thứ k mà không sort toàn bộ mảng. Yêu cầu: average time O(n).

Input: nums = [3, 2, 1, 5, 6, 4], k = 2Output: 5

💡 Gợi ý

Phần tử lớn thứ k = phần tử nhỏ thứ n - k (0-indexed)
Dùng Quick Select: partition rồi chỉ đệ quy vào nửa chứa vị trí cần tìm
Random pivot để tránh worst case

✅ Lời giải

python

import random

def find_kth_largest(nums: list[int], k: int) -> int:
    target = len(nums) - k  # chuyển thành tìm phần tử nhỏ thứ target

    def select(low: int, high: int) -> int:
        pivot_idx = random.randint(low, high)
        nums[pivot_idx], nums[high] = nums[high], nums[pivot_idx]

        pivot = nums[high]
        store = low
        for i in range(low, high):
            if nums[i] <= pivot:
                nums[store], nums[i] = nums[i], nums[store]
                store += 1
        nums[store], nums[high] = nums[high], nums[store]

        if store == target:
            return nums[store]
        elif store < target:
            return select(store + 1, high)
        else:
            return select(low, store - 1)

    return select(0, len(nums) - 1)

Phân tích: Average O(n), worst O(n²) nhưng random pivot khiến worst case gần như không xảy ra. Space O(log n) cho stack đệ quy. Đây chính là cách numpy.partition hoạt động bên trong.

Liên kết học tiếp

Từ khóa glossary: Quick Sort, partition, pivot, Lomuto, Hoare, in-place sort, divide and conquer, Quick Select, introsort, Dutch National Flag

Tìm kiếm liên quan: sắp xếp nhanh, thuật toán chia để trị, tìm phần tử thứ k, 3-way partition

Quick Sort — Sắp xếp nhanh ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Partition — trái tim của Quick Sort ​

Lomuto Partition Scheme ​

Hoare Partition Scheme ​

Chiến lược chọn Pivot ​

3-Way Partition — Dutch National Flag ​

Thực chiến ​

Tình huống 1: Quick Select — tìm phần tử lớn thứ k trong O(n) ​

Tình huống 2: Introsort — Quick Sort trong thực tế production ​

Sai lầm điển hình ​

❌ Sai lầm 1: Chọn pivot cố định trên mảng đã sắp xếp ​

❌ Sai lầm 2: Stack overflow với đệ quy sâu ​

❌ Sai lầm 3: Không xử lý mảng toàn phần tử giống nhau ​

❌ Sai lầm 4: Nhầm lẫn đệ quy giữa Lomuto và Hoare ​

❌ Sai lầm 5: Không switch sang Insertion Sort cho mảng nhỏ ​

Under the Hood ​

Hiệu năng ​

Tại sao worst case gần như không xảy ra với random pivot ​

Tại sao Quick Sort thắng Merge Sort trong thực tế ​

Introsort: Quick Sort không sợ worst case ​

Trade-offs ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: Sort Colors (Dutch National Flag) — Foundation ​

Bài 2: Kth Largest Element — Intermediate ​

Liên kết học tiếp ​

Quick Sort — Sắp xếp nhanh

Bức tranh tư duy

Cốt lõi kỹ thuật

Partition — trái tim của Quick Sort

Lomuto Partition Scheme

Hoare Partition Scheme

Chiến lược chọn Pivot

3-Way Partition — Dutch National Flag

Thực chiến

Tình huống 1: Quick Select — tìm phần tử lớn thứ k trong O(n)

Tình huống 2: Introsort — Quick Sort trong thực tế production

Sai lầm điển hình

❌ Sai lầm 1: Chọn pivot cố định trên mảng đã sắp xếp

❌ Sai lầm 2: Stack overflow với đệ quy sâu

❌ Sai lầm 3: Không xử lý mảng toàn phần tử giống nhau

❌ Sai lầm 4: Nhầm lẫn đệ quy giữa Lomuto và Hoare

❌ Sai lầm 5: Không switch sang Insertion Sort cho mảng nhỏ

Under the Hood

Hiệu năng

Tại sao worst case gần như không xảy ra với random pivot

Tại sao Quick Sort thắng Merge Sort trong thực tế

Introsort: Quick Sort không sợ worst case

Trade-offs

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: Sort Colors (Dutch National Flag) — Foundation

Bài 2: Kth Largest Element — Intermediate

Liên kết học tiếp