Quick Sort (Sắp Xếp Nhanh)

Đúng như tên gọi, Quick Sort thường là thuật toán nhanh nhất trong thực tế. Nó cũng dùng chiến thuật Divide and Conquer, nhưng khác Merge Sort ở chỗ nó thực hiện phần việc khó nhọc ở bước Chia (Partition) chứ không phải bước Gộp.

Khái Niệm Quan Trọng: The Pivot (Chốt)

Toàn bộ thuật toán xoay quanh việc chọn một phần tử làm Pivot và sắp xếp lại mảng sao cho:

• Tất cả phần tử nhỏ hơn Pivot chuyển về bên trái.
• Tất cả phần tử lớn hơn Pivot chuyển về bên phải.

Sau bước này, Pivot đang đứng đúng vị trí cuối cùng của nó trong mảng đã sắp xếp.

Minh Họa Partition (Lomuto Scheme)

Giả sử chọn Pivot là phần tử cuối cùng [4]. Mảng: [2, 8, 7, 1, 3, 5, 6, 4]

Pivot = 4
Quét mảng từ trái sang phải. Tìm số <= 4 để ném sang vùng bên trái.
[2] <= 4 -> Giữ vùng trái.
[8] > 4 -> Chờ swap.
[7] > 4 -> Chờ swap.
[1] <= 4 -> Swap với [8] (số lớn đầu tiên gặp). Mảng: [2, 1, 7, 8, ...]
[3] <= 4 -> Swap với [7]. Mảng: [2, 1, 3, 8, 7, ...]
...
Cuối cùng đưa Pivot vào giữa: [2, 1, 3, 4, 7, 5, 6, 8]
Pivot [4] giờ đã yên vị.

Code Implementation

Chúng ta sẽ dùng Lomuto Partition Scheme vì nó dễ hiểu và dễ cài đặt.

C++

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1); // Chỉ số của phần tử nhỏ hơn

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

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);
    }
}

Java

class QuickSort {
    int partition(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++;
                // Swap arr[i] và arr[j]
                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;
    }

    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);
        }
    }
}

Python

def partition(arr, low, high):
    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(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

🛑 HPN's Warning

Quick Sort có một tử huyệt: Worst Case O(N^2). Điều này xảy ra khi mảng ĐÃ SẮP XẾP SẴN (hoặc ngược lại) và ta cứ chọn phần tử cuối cùng làm Pivot. Giải pháp: Luôn chọn Pivot ngẫu nhiên (Randomized Quick Sort) hoặc chọn phần tử trung vị (Median-of-three) để tránh trường hợp đen đủi này.

✦

✧

✦

👑PREMIUM

HPN Interview Kit

Bộ câu hỏi phỏng vấn Big Tech

• ✓ 200+ câu hỏi thực tế từ FAANG
• ✓ Giải thích chi tiết bằng Tiếng Việt
• ✓ Cập nhật liên tục 2025

Sở hữu ngay99k