Chương trình C++ triển khai Quick Sort với ràng buộc độ phức tạp

Quick Sort dựa trên chiến lược Chia để trị (Divide-and-Conquer). Độ phức tạp thời gian trung bình của thuật toán này là O(n log n) nhưng trường hợp xấu nhất là O(n²). Để giảm thiểu khả năng xảy ra trường hợp xấu, Quick Sort được triển khai với kỹ thuật ngẫu nhiên hóa (randomization) chọn pivot.

Thuật toán

partition(int a[], int l, int h)

Bắt đầu
  pivot = h
  index = l
  start = l và end = h
  trong khi start < end làm
    trong khi a[start] <= pivot VÀ start < end làm
      start = start + 1
    xong
    trong khi a[end] > pivot làm
      end = end - 1
    xong
    nếu start < end thì
      hoán đổi a[start] với a[end]
    xong
    a[low] = a[end]
    a[end] = pivot
  trả về end
Kết thúc

RandomPivotPartition(int a[], int l, int h)

Bắt đầu
  n = rand()
  pivot = l + n % (h - l + 1)
  Hoán đổi a[h] với a[pivot]
  trả về Partition(a, l, h)
Kết thúc

QuickSort(int a[], int l, int h)

Bắt đầu
  int pindex;
  Nếu (l < h)
    pindex = RandomPivotPartition(a, l, h)
    QuickSort(a, l, pindex-1)
    QuickSort(a, pindex+1, h)
  trả về 0
Kết thúc

Mã ví dụ

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

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

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

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

int QuickSort(int a[], int l, int h) {
    int pindex;
    if (l < h) {
        pindex = RandomPivotPartition(a, l, h);
        QuickSort(a, l, pindex-1);
        QuickSort(a, pindex+1, h);
    }
    return 0;
}

int main() {
    int n, i;
    cout << "\nNhập số lượng phần tử dữ liệu cần sắp xếp: ";
    cin >> n;
    int arr[n];
    for (i = 0; i < n; i++) {
        cout << "Nhập phần tử " << i+1 << ": ";
        cin >> arr[i];
    }
    QuickSort(arr, 0, n-1);
    cout << "\nDữ liệu đã sắp xếp ";
    for (i = 0; i < n; i++)
        cout << "->" << arr[i];
    return 0;
}

Kết quả

Nhập số lượng phần tử dữ liệu cần sắp xếp: 4
Nhập phần tử 1: 3
Nhập phần tử 2: 4
Nhập phần tử 3: 7
Nhập phần tử 4: 6
Dữ liệu đã sắp xếp ->3->4->6->7