Sắp xếp Quicksort

Quicksort là thuật toán sắp xếp có độ phức tạp trung bình \(O(nlog(n))\) được sử dụng phổ biến do tính đơn giản khi cài đặt và tốc độ thực thi nhanh. Tuy nhiên, trong cài đặt cần chọn điểm chốt tốt nếu không thuật toán sẽ rơi vào độ phức tạp \(O(n^2)\), thông thường ta sẽ chọn điểm chốt ngẫu nhiên để tránh trường hợp này.

Thuật toán

Quicksort sử dụng tư tưởng chia để trị để sắp xếp lại mảng \(A\) trong đoạn từ \(l\) đến \(r\) như sau:

• Sắp xếp và chia mảng \(A[l..r]\) thành hai phần \(A[l..q-1]\) và \(A[q+1..r]\) sao cho mỗi phần tử trong \(A[l..q-1]\) đều nhỏ hơn hoặc bằng \(A[q]\), do đó cũng nhỏ hơn hoặc bằng các phần tử trong \(A[q+1, r]\).
• Gọi đệ quy để sắp xếp \(A[l..q-1]\) và \(A[q+1..r]\).
• Sau khi gọi đệ quy, cả hai mảng con đều đã được sắp xếp nên \(A[l..r]\) cũng đã được sắp xếp.

Cài đặt

Trong cài đặt sau, để cho đơn giản ta sẽ chọn điểm chốt là phần tử ở giữa đoạn đang xét.

#include <vector>
using namespace std;

void qsort(vector<int> &a, int l, int r) {
    if (l>=r) return;
    int i = l,
        j = r,
        x = a[(l+r)/2];
    while (i<=j) {
        while (a[i]<x) i++;
        while (a[j]>x) j--;
        if (i<=j) swap(a[i++], a[j--]);
    }
    qsort(a, l, j);
    qsort(a, i, r);
}

int main() {
    vector<int> a = {3, 5, -2, 4, 6, 2, 0, 1, 4};
    qsort(a, 0, a.size()-1);
    return 0;
}