Thuật toán Quick Sort (Sắp xếp nhanh)

Quick Sort chia mảng thành 2 phần bằng thuật toán partition chọn pivot. Phần trái pivot chứa giá trị ≤ pivot, phần phải chứa giá trị > pivot. Đệ quy sắp xếp 2 phần con.

Độ phức tạp Quick Sort

• Time Complexity: O(n log n) tốt và trung bình, O(n²) xấu nhất
• Space Complexity: O(log n) (stack đệ quy)

Input và Output

Input: Danh sách chưa sắp xếp: 90 45 22 11 22 50
Output: Mảng trước: 90 45 22 11 22 50
Mảng sau: 11 22 22 45 50 90

Thuật toán

partition(array, lower, upper) - Hoare partition

Begin
  pivot := array[lower]
  start := lower, end := upper
  while start < end do
    while array[start] <= pivot AND start < end do start++ done
    while array[end] > pivot do end-- done
    if start < end then swap array[start] with array[end] done
  done
  array[lower] := array[end]
  array[end] := pivot
  return end
End

quickSort(array, left, right)

Begin
  if left < right then
    q = partition(array, left, right)
    quickSort(array, left, q-1)
    quickSort(array, q+1, right)
  End

Ví dụ (C++)

#include <iostream>
using namespace std;

void swapping(int &a, int &b) { int t=a; a=b; b=t; }
void display(int *a, int n) { for(int i=0;i pivot) end--;
        if(start < end) swapping(a[start], a[end]);
    }
    a[low] = a[end]; a[end] = pivot; return end;
}

void quickSort(int *a, int left, int right) {
    if(left < right) {
        int q = partition(a, left, right);
        quickSort(a, left, q-1);
        quickSort(a, q+1, right);
    }
}

int main() {
    int n; cout << "Số phần tử: "; cin >> n;
    int arr[n];
    for(int i=0;i> arr[i];
    cout << "Trước: "; display(arr,n);
    quickSort(arr, 0, n-1);
    cout << "Sau: "; display(arr,n);
}

Kết quả

Số phần tử: 6
Nhập phần tử: 90 45 22 11 22 50
Trước: 90 45 22 11 22 50
Sau: 11 22 22 45 50 90

Cải tiến: Chọn pivot ngẫu nhiên hoặc median-of-three để tránh worst-case O(n²) trên mảng đã sắp xếp. Dùng Insertion Sort cho mảng con nhỏ (≤10 phần tử). Tail recursion elimination giảm stack space.