Chương trình C++ cho thuật toán QuickSort

QuickSort là kỹ thuật sắp xếp sử dụng so sánh để sắp xếp danh sách chưa sắp xếp (mảng). Còn gọi là Partition Exchange Sort (Sắp xếp trao đổi phân vùng).

QuickSort không ổn định (unstable) vì thứ tự tương đối của các phần tử bằng nhau không được bảo toàn. QuickSort hoạt động trên mảng, chỉ cần lượng bộ nhớ phụ nhỏ. Nó tương tự Selection Sort nhưng không luôn chọn phân vùng xấu nhất, nên hiệu quả hơn.

QuickSort là một trong những thuật toán sắp xếp hiệu quả nhất, dựa trên việc chia mảng thành các mảng con nhỏ hơn. Tên gọi đến từ việc nó sắp xếp nhanh hơn đáng kể so với các thuật toán phổ biến. Giống Merge Sort, Quick Sort cũng áp dụng chiến lược Chia để trị (Divide and Conquer).

Cách hoạt động của QuickSort

• Chọn giá trị chốt (Pivot) - ví dụ chọn phần tử cuối.
• Phân vùng mảng: phần tử < pivot bên trái, > pivot bên phải.
• Đệ quy áp dụng cho hai mảng con bên trái và bên phải pivot.
• Khi mảng con còn 1 phần tử thì đã sắp xếp xong.

Ví dụ minh họa

Input: arr[] = {7, 4, 2, 6, 3, 1, 5}
Output: 1 2 3 4 5 6 7

Giải thích chi tiết (mảng: 50, 23, 9, 18, 61, 32)

Bước 1: Chọn pivot = 32 (phần tử cuối). Low=0 (50), High=5 (32).

Duyệt từ đầu: 50 > 32 (giữ), 23 < 32 (hoán đổi với 50) → 23, 50, 9, 18, 61, 32

Tiếp: 9 < 32 (hoán đổi với 50) → 23, 9, 50, 18, 61, 32

18 < 32 (hoán đổi với 50) → 23, 9, 18, 50, 61, 32

61 > 32 (giữ). Cuối cùng hoán đổi pivot (32) với 50 → 23, 9, 18, 32, 61, 50

Pivot 32 đã ở đúng vị trí. Phía trái < 32, phía phải > 32.

Bước 2-4: Đệ quy cho mảng con [23, 9, 18] và [61, 50]. Kết quả cuối: 9, 18, 23, 32, 50, 61.

Code ví dụ (có Random Pivot)

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

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

int Partition(int a[], int low, int high) {
    int pivot = high;
    int index = low;
    for(int i = low; i < high; i++) {
        if(a[i] < a[pivot]) {
            swap(&a[i], &a[index]);
            index++;
        }
    }
    swap(&a[pivot], &a[index]);
    return index;
}

int RandomPivotPartition(int a[], int low, int high) {
    int pvt = low + rand() % (high - low + 1);
    swap(&a[high], &a[pvt]);
    return Partition(a, low, high);
}

void QuickSort(int a[], int low, int high) {
    if (low < high) {
        int pindex = RandomPivotPartition(a, low, high);
        QuickSort(a, low, pindex - 1);
        QuickSort(a, pindex + 1, high);
    }
}

int main() {
    srand(time(0));
    int arr[] = {7, 4, 2, 6, 3, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    QuickSort(arr, 0, n - 1);
    
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Độ phức tạp

• Trung bình: O(n log n)
• Tốt nhất: O(n log n)
• Xấu nhất: O(n²) (khi pivot luôn là max/min)
• Không gian: O(log n) do đệ quy