- Giới thiệu
- Cơ chế hoạt động
- Cài đặt Quick Sort trong C++
- Phân tích độ phức tạp
- Ưu và nhược điểm
- So sánh với các thuật toán sắp xếp khác
- Các biến thể của Quick Sort
- Bài tập thực hành
- Tổng kết
Quick Sort (sắp xếp nhanh) là một thuật toán sắp xếp hiệu quả dựa trên nguyên lý "chia để trị" (divide and conquer). Thuật toán này được phát triển bởi Tony Hoare vào năm 1959 và được xuất bản vào năm 1961.
Đặc điểm nổi bật của Quick Sort:
- Hiệu quả cao: Trong trường hợp trung bình, Quick Sort có độ phức tạp O(n log n)
- Sắp xếp tại chỗ: Không cần bộ nhớ phụ lớn
- Không ổn định: Các phần tử có giá trị bằng nhau có thể bị đảo vị trí sau khi sắp xếp
Quick Sort được sử dụng rộng rãi trong thực tế và là thuật toán sắp xếp mặc định trong nhiều thư viện như C++ STL's std::sort(), Java's Arrays.sort() và Python's sorted().
Quick Sort hoạt động theo nguyên lý "chia để trị" với các bước cơ bản sau:
- Chọn phần tử chốt (pivot): Chọn một phần tử từ mảng làm phần tử chốt.
- Phân hoạch (partition): Sắp xếp lại mảng sao cho:
- Tất cả các phần tử nhỏ hơn pivot nằm trước pivot
- Tất cả các phần tử lớn hơn pivot nằm sau pivot
- Pivot nằm ở vị trí chính xác của nó trong mảng đã sắp xếp
- Đệ quy: Áp dụng đệ quy Quick Sort cho các mảng con trước và sau pivot
Giả sử chúng ta có mảng: [7, 2, 1, 6, 8, 5, 3, 4]
Chúng ta chọn phần tử cuối cùng làm pivot: pivot = 4
Sắp xếp lại mảng để tất cả phần tử < 4 nằm bên trái và các phần tử > 4 nằm bên phải:
- Đầu tiên:
[7, 2, 1, 6, 8, 5, 3, 4] - Sau khi phân hoạch:
[2, 1, 3, 4, 8, 5, 6, 7]
Lúc này, pivot (4) đã ở đúng vị trí của nó.
- Áp dụng Quick Sort cho mảng con bên trái:
[2, 1, 3] - Áp dụng Quick Sort cho mảng con bên phải:
[8, 5, 6, 7]
Quá trình tiếp tục cho đến khi tất cả các mảng con có kích thước là 0 hoặc 1.
#include <iostream>
#include <vector>
using namespace std;
// Hàm hoán đổi hai phần tử
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
// Hàm phân hoạch mảng và trả về vị trí của pivot
int partition(vector<int> &arr, int low, int high) {
int pivot = arr[high]; // Chọn phần tử cuối làm pivot
int i = low - 1; // Chỉ số của phần tử nhỏ hơn
for (int j = low; j < high; j++) {
// Nếu phần tử hiện tại nhỏ hơn pivot
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
// Đặt pivot vào đúng vị trí
swap(arr[i + 1], arr[high]);
return i + 1;
}
// Hàm Quick Sort đệ quy
void quickSort(vector<int> &arr, int low, int high) {
if (low < high) {
// pi là vị trí phân hoạch, arr[pi] ở đúng vị trí
int pi = partition(arr, low, high);
// Sắp xếp đệ quy các phần tử trước và sau vị trí phân hoạch
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Hàm chính để gọi Quick Sort
void quickSort(vector<int> &arr) {
quickSort(arr, 0, arr.size() - 1);
}
// Hàm in mảng
void printArray(const vector<int> &arr) {
for (int num : arr) {
cout << num << " ";
}
cout << endl;
}
// Ví dụ sử dụng
int main() {
vector<int> arr = {7, 2, 1, 6, 8, 5, 3, 4};
cout << "Mảng ban đầu: ";
printArray(arr);
quickSort(arr);
cout << "Mảng sau khi sắp xếp: ";
printArray(arr);
return 0;
}int medianOfThree(vector<int> &arr, int low, int high) {
int mid = low + (high - low) / 2;
// Sắp xếp arr[low], arr[mid], arr[high]
if (arr[low] > arr[mid])
swap(arr[low], arr[mid]);
if (arr[low] > arr[high])
swap(arr[low], arr[high]);
if (arr[mid] > arr[high])
swap(arr[mid], arr[high]);
// arr[mid] là giá trị trung vị, đặt nó ở vị trí high-1
swap(arr[mid], arr[high - 1]);
return arr[high - 1];
}
int optimizedPartition(vector<int> &arr, int low, int high) {
// Sử dụng median-of-three để chọn pivot
int pivot = medianOfThree(arr, low, high);
int i = low;
int j = high - 1;
while (true) {
while (arr[++i] < pivot);
while (arr[--j] > pivot);
if (i >= j)
break;
swap(arr[i], arr[j]);
}
swap(arr[i], arr[high - 1]); // Đặt pivot vào vị trí cuối cùng
return i;
}void insertionSort(vector<int> &arr, int low, int high) {
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
void optimizedQuickSort(vector<int> &arr, int low, int high) {
const int CUTOFF = 10; // Ngưỡng chuyển sang Insertion Sort
if (high - low + 1 <= CUTOFF) {
insertionSort(arr, low, high);
return;
}
if (low < high) {
int pi = optimizedPartition(arr, low, high);
optimizedQuickSort(arr, low, pi - 1);
optimizedQuickSort(arr, pi + 1, high);
}
}#include <stack>
void iterativeQuickSort(vector<int> &arr, int low, int high) {
// Tạo một stack để lưu trữ các khoảng cần sắp xếp
stack<pair<int, int>> st;
st.push({low, high});
// Xử lý các khoảng cho đến khi stack rỗng
while (!st.empty()) {
// Lấy khoảng từ stack
low = st.top().first;
high = st.top().second;
st.pop();
// Phân hoạch mảng
int pi = partition(arr, low, high);
// Nếu có phần tử bên trái của pivot, đẩy vào stack
if (pi - 1 > low)
st.push({low, pi - 1});
// Nếu có phần tử bên phải của pivot, đẩy vào stack
if (pi + 1 < high)
st.push({pi + 1, high});
}
}-
Trường hợp tốt nhất (Best case): O(n log n)
- Xảy ra khi pivot luôn chia mảng thành hai phần bằng nhau
-
Trường hợp trung bình (Average case): O(n log n)
- Phân tích xác suất cho thấy, trung bình mỗi lần phân hoạch không tạo ra mảng quá mất cân bằng
-
Trường hợp xấu nhất (Worst case): O(n²)
- Xảy ra khi pivot luôn là phần tử lớn nhất hoặc nhỏ nhất của mảng
- Hoặc khi mảng đã được sắp xếp và pivot luôn được chọn là phần tử đầu hoặc cuối
-
Trường hợp tốt nhất và trung bình: O(log n)
- Không gian cho ngăn xếp đệ quy
-
Trường hợp xấu nhất: O(n)
- Khi mảng mất cân bằng hoàn toàn, độ sâu đệ quy có thể lên đến n
- Hiệu quả cao trong trường hợp trung bình với độ phức tạp O(n log n)
- Sắp xếp tại chỗ (in-place), không yêu cầu bộ nhớ phụ lớn
- Phân hoạch chia nhỏ vấn đề giúp tận dụng bộ nhớ cache
- Hiệu suất tốt với các tập dữ liệu lớn
- Độ phức tạp xấu nhất là O(n²)
- Không ổn định (unstable) - không bảo toàn thứ tự tương đối của các phần tử có giá trị bằng nhau
- Hiệu suất phụ thuộc nhiều vào việc chọn pivot
- Đệ quy sâu có thể gây tràn ngăn xếp với dữ liệu lớn
| Thuật toán | Thời gian trung bình | Thời gian xấu nhất | Không gian | Ổn định |
|---|---|---|---|---|
| Quick Sort | O(n log n) | O(n²) | O(log n) | Không |
| Merge Sort | O(n log n) | O(n log n) | O(n) | Có |
| Heap Sort | O(n log n) | O(n log n) | O(1) | Không |
| Insertion Sort | O(n²) | O(n²) | O(1) | Có |
| Bubble Sort | O(n²) | O(n²) | O(1) | Có |
Dual-Pivot Quick Sort sử dụng hai pivot thay vì một, giúp phân hoạch mảng thành ba phần. Đây là thuật toán được sử dụng trong Arrays.sort() của Java.
void dualPivotQuickSort(vector<int> &arr, int low, int high) {
if (high <= low)
return;
// Đảm bảo pivot1 <= pivot2
if (arr[low] > arr[high])
swap(arr[low], arr[high]);
int pivot1 = arr[low];
int pivot2 = arr[high];
int lt = low + 1; // Chỉ số cho phần tử < pivot1
int gt = high - 1; // Chỉ số cho phần tử > pivot2
int i = low + 1; // Iterator
while (i <= gt) {
if (arr[i] < pivot1) {
swap(arr[i], arr[lt]);
lt++;
i++;
}
else if (arr[i] > pivot2) {
swap(arr[i], arr[gt]);
gt--;
}
else {
i++;
}
}
lt--;
gt++;
swap(arr[low], arr[lt]);
swap(arr[high], arr[gt]);
// Đệ quy cho ba phần
dualPivotQuickSort(arr, low, lt - 1);
dualPivotQuickSort(arr, lt + 1, gt - 1);
dualPivotQuickSort(arr, gt + 1, high);
}Randomized Quick Sort chọn pivot ngẫu nhiên để tránh trường hợp xấu nhất.
#include <cstdlib>
#include <ctime>
int randomPartition(vector<int> &arr, int low, int high) {
// Tạo số ngẫu nhiên trong khoảng [low, high]
srand(time(nullptr));
int random = low + rand() % (high - low + 1);
// Đổi phần tử ngẫu nhiên với phần tử cuối
swap(arr[random], arr[high]);
return partition(arr, low, high);
}
void randomizedQuickSort(vector<int> &arr, int low, int high) {
if (low < high) {
int pi = randomPartition(arr, low, high);
randomizedQuickSort(arr, low, pi - 1);
randomizedQuickSort(arr, pi + 1, high);
}
}Three-way Quick Sort hiệu quả với mảng có nhiều phần tử trùng lặp.
void threeWayQuickSort(vector<int> &arr, int low, int high) {
if (high <= low)
return;
int lt = low; // Chỉ số cho phần tử < pivot
int gt = high; // Chỉ số cho phần tử > pivot
int i = low + 1; // Iterator
int pivot = arr[low];
while (i <= gt) {
if (arr[i] < pivot) {
swap(arr[lt], arr[i]);
lt++;
i++;
}
else if (arr[i] > pivot) {
swap(arr[i], arr[gt]);
gt--;
}
else {
i++;
}
}
threeWayQuickSort(arr, low, lt - 1);
threeWayQuickSort(arr, gt + 1, high);
}Yêu cầu: Viết chương trình C++ cài đặt thuật toán Quick Sort để sắp xếp một mảng số nguyên theo thứ tự tăng dần.
Đầu vào: Mảng số nguyên Đầu ra: Mảng đã sắp xếp
Yêu cầu: Điều chỉnh thuật toán Quick Sort để sắp xếp mảng theo thứ tự giảm dần.
Yêu cầu: Viết chương trình C++ sử dụng Quick Sort để sắp xếp một mảng các sinh viên theo điểm trung bình (tăng dần).
struct Student {
string name;
double gpa;
};Yêu cầu: Sử dụng ý tưởng của thuật toán Quick Sort để tìm phần tử có giá trị nhỏ thứ k trong mảng.
Gợi ý: Sử dụng hàm phân hoạch của Quick Sort và chỉ đệ quy vào một nửa của mảng.
Yêu cầu: Điều chỉnh thuật toán Quick Sort để đếm số lần so sánh cần thiết để sắp xếp mảng.
Yêu cầu: So sánh hiệu suất của các biến thể Quick Sort khác nhau (cơ bản, randomized, và three-way) với các tập dữ liệu khác nhau:
- Mảng đã sắp xếp
- Mảng ngẫu nhiên
- Mảng có nhiều phần tử trùng lặp
Yêu cầu: So sánh hiệu suất của Quick Sort tự cài đặt với hàm std::sort() của thư viện chuẩn C++.
Yêu cầu: Triển khai phiên bản tối ưu của Quick Sort kết hợp các kỹ thuật:
- Median-of-three cho việc chọn pivot
- Insertion Sort cho mảng con nhỏ
- Thuật toán không đệ quy để tránh tràn ngăn xếp
Yêu cầu: Cài đặt thuật toán Hybrid Quick Sort kết hợp Quick Sort với Insertion Sort cho các mảng con có kích thước nhỏ hơn một ngưỡng cho trước.
Yêu cầu: Cài đặt thuật toán Quick Sort song song sử dụng thư viện thread của C++11 hoặc OpenMP để tăng tốc quá trình sắp xếp trên các máy tính đa lõi.
Quick Sort là một thuật toán sắp xếp hiệu quả với độ phức tạp trung bình O(n log n), phù hợp cho nhiều ứng dụng thực tế. Mặc dù có trường hợp xấu nhất là O(n²), nhưng với các kỹ thuật tối ưu hóa như chọn pivot ngẫu nhiên hoặc median-of-three, xác suất gặp trường hợp xấu nhất rất thấp.
Thuật toán Quick Sort đã được nghiên cứu và tối ưu hóa rộng rãi, dẫn đến nhiều biến thể hiệu quả như Dual-Pivot Quick Sort, Three-Way Quick Sort, và các phiên bản hybrid kết hợp với các thuật toán sắp xếp khác.
Để áp dụng Quick Sort hiệu quả trong thực tế, hãy cân nhắc:
- Sử dụng kỹ thuật chọn pivot tốt
- Chuyển sang Insertion Sort cho các mảng con nhỏ
- Sử dụng phiên bản không đệ quy cho dữ liệu lớn
- Cân nhắc các biến thể phù hợp với đặc điểm dữ liệu (nhiều phần tử trùng lặp, gần sắp xếp, v.v.)
Nắm vững Quick Sort và các biến thể của nó sẽ giúp bạn có thêm một công cụ mạnh mẽ trong bộ công cụ thuật toán của mình.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
- Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley Professional.
- Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley Professional.