Sắp xếp · Chia để trị · Đệ quy

Quick Sort

Thuật toán sắp xếp nhanh nhất trong thực tế — chọn một pivot, phân vùng mảng, rồi đệ quy sắp xếp hai nửa. Trung bình O(n log n).

● Medium Best/Avg: O(n log n)Worst: O(n²)Space: O(log n)Unstable ✗

Tốc độ

Chưa xử lý Pivot Con trỏ i Con trỏ j Hoán đổi Đã sắp xong

So sánh0

Hoán đổi0

Gọi đệ quy0

Nhấn Chạy hoặc Bước kế...

Ý tưởng — Partition

Quick Sort hoạt động theo nguyên tắc Divide & Conquer (chia để trị):

Chọn pivot: chọn một phần tử làm "chốt" (thường là phần tử cuối)
Partition: sắp xếp lại mảng sao cho tất cả phần tử < pivot nằm bên trái, > pivot nằm bên phải
Đệ quy: áp dụng Quick Sort cho nửa trái và nửa phải

💡

Tại sao nhanh? Quick Sort tận dụng tốt cache CPU (locality of reference) và có hệ số nhân nhỏ hơn Merge Sort. Trung bình chỉ cần ~1.39n log n so sánh — nhanh hơn đáng kể trong thực tế dù cùng O(n log n).

Cài đặt C — Lomuto Partition

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

/* Lomuto partition: pivot = a[hi]
   Trả về chỉ số cuối cùng của pivot */
int partition(int a[], int lo, int hi) {
    int pivot = a[hi];
    int i     = lo - 1; /* ranh giới vùng nhỏ hơn pivot */

    for (int j = lo; j < hi; j++) {
        if (a[j] <= pivot) {
            i++;
            swap(&a[i], &a[j]);
        }
    }
    swap(&a[i + 1], &a[hi]); /* đặt pivot vào đúng vị trí */
    return i + 1;
}

void quickSort(int a[], int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        quickSort(a, lo,     p - 1); /* nửa trái  */
        quickSort(a, p + 1, hi    ); /* nửa phải */
    }
}

int main() {
    int a[] = {10, 80, 30, 90, 40, 50, 70};
    int n = sizeof(a) / sizeof(a[0]);
    quickSort(a, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    /* Output: 10 30 40 50 70 80 90 */
    return 0;
}

Cài đặt C — Hoare Partition (hiệu quả hơn)

/* Hoare partition: ít hoán đổi hơn Lomuto ~3x */
int hoarePartition(int a[], int lo, int hi) {
    int pivot = a[lo + (hi - lo) / 2]; /* pivot giữa */
    int i = lo - 1, j = hi + 1;

    while (true) {
        do { i++; } while (a[i] < pivot);
        do { j--; } while (a[j] > pivot);
        if (i >= j) return j;
        swap(&a[i], &a[j]);
    }
}

Độ phức tạp

Trường hợp	Thời gian	Không gian	Ghi chú
Tốt nhất	O(n log n)	O(log n)	Pivot luôn chia đôi mảng
Trung bình	O(n log n)	O(log n)	~1.39n log n so sánh
Tệ nhất	O(n²)	O(n)	Mảng đã sắp + pivot = phần tử đầu/cuối

⚠️

Tránh worst case: Chọn pivot ngẫu nhiên (randomized pivot) hoặc dùng "median-of-3" (trung vị của 3 phần tử đầu/giữa/cuối) để tránh O(n²) trên mảng đã sắp.

← TrướcInsertion Sort Tiếp →Heap Sort