Giới thiệu
Thuật toán Quick Sort (Sắp xếp nhanh) là một trong những thuật toán sắp xếp hiệu quả nhất và dựa trên việc chia một mảng thành các mảng nhỏ hơn. Sắp xếp nhanh có khả năng sắp xếp danh sách các yếu tố dữ liệu nhanh hơn đáng kể so với bất kỳ thuật toán sắp xếp phổ biến nào. Nếu so với các thuật toán sắp xếp phổ biến như Insertion Sort, Selection Sort hay Bubble Sort, thì Quick Sort cho một hiệu năng đáng kể.
Ý tưởng
Giống như Merge Sort, Quick Sort là thuật toán chia để trị (Divide and Conquer). Thuật toán sẽ chọn một phần tử trong chuỗi, mảng để làm điểm đánh dấu (pivot). Sau khi lựa chọn được điểm đánh dấu (pivot), thuật toán sẽ thực hiện chia mảng thành các mảng con, công việc này gọi là phân đoạn (partition). Và lặp đi lặp lại như vậy cho đến khi kết thúc.
Vì thế hiệu suất của Quick Sort phụ thuộc vào các lựa chọn điểm đánh dấu pivot và thuật toán phân đoạn. Nếu lựa chọn pivot tốt thì thuật toán sẽ có tốc độ nhanh hơn.
Cách lựa chọn Pivot
Trong một mảng, dãy số cho trước, chúng ta có thể lựa chọn pivot bằng các cách sau:
- Chọn phần tử đầu tiên của mảng
- Chọn phần tử cuối cùng của mảng
- Chọn 1 phần tử ngẫu nhiên của mảng
- Chọn số trung vị của mảng (Median element)
Thuật toán phân đoạn (Partition)
Quan trọng chính của thuật toán sắp xếp Quick Sort là việc phân đoạn dãy số. Công việc chính của việc phân đoạn là:
- Cho một mảng và xác định phần tử X là pivot
- Đặt X vào đúng vị trí của mảng đã sắp xếp
- Di chuyển tất cả các phần tử của mảng nhỏ hơn X sang bên trái và lớn hơn sang bên phải
Khi đó ta sẽ có 2 mảng con: mảng bên trái của X và mảng bên phải của X. Tiếp tục công việc với mỗi mảng con (chọn pivot, phân đoạn) cho tới khi mảng được sắp xếp.
Cài đặt
class QuickSort {
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low-1);
for (int j=low; jKết quả là một mảng được sắp xếp hoàn chỉnh: 1 5 7 8 9 10
Đánh giá thuật toán sắp xếp nhanh
Độ phức tạp thuật toán:
- Trường hợp tốt: O(n*log(n))
- Trung bình: O(n*log(n))
- Trường hợp xấu: O(n^2)
Không gian bộ nhớ sử dụng: O(log(n))
Ổn định (Stable): Không
Tại chỗ (In-place): Có
Cách sử dụng:
- Quick Sort được sử dụng ở mọi nơi mà không cần sự ổn định
- Nhiều biến thể của Quick Sort được sử dụng để phân tách k phần tử nhỏ nhất hoặc lớn nhất
- Thuật toán chia để trị của Quick Sort cho phép sử dụng song song
- Quick Sort là thuật toán sắp xếp khá thân thiện với bộ nhớ đệm vì nó tham chiếu trực tiếp tới mảng mà không cần thêm bộ nhớ để lưu trữ
