Quick sort và ứng dụng của nó

Ở bài trước mình đã đề cập đến một vài thuật toán sắp xếp đó là Bogo sort, Bubble sort, Selection sort và Merge sort. Ở bài này mình xin được phép đề cập đến 1 thuật toán được sử dụng khá rộng rãi hiện nay (tuy không phải tối ưu nhất) đó là Quick sort:

Khái niệm Quick sort

Quick sort được phát triển bởi Tony Hoare và được công bố năm 1961, kế hoạch của thuật toán này như sau:

Chọn 1 phần tử chốt trong dãy, những phần tử nhỏ hơn nó đưa lên trên, ngược lại đẩy xuống dưới. Tiếp tục lặp lại quy trình với 2 mảng con phía 2 bên của phần tử chốt.

Khác với Merge sort, quick sort chia danh sách cần sắp xếp $a \begin{bmatrix} 1, n\end{bmatrix}$ thành hai danh sách con có kích thước tương đối bằng nhau nhờ chỉ số đứng giữa danh sách, sắp xếp nhanh chia nó thành hai danh sách bằng cách so sánh từng phần tử của danh sách với một phần tử được chọn được gọi là phần tử chốt. Những phần tử nhỏ hơn hoặc bằng phần tử chốt được đưa về phía trước và nằm trong danh sách con thứ nhất, các phần tử lớn hơn chốt được đưa về phía sau và thuộc danh sách đứng sau. Cứ tiếp tục chia như vậy tới khi các danh sách con đều có độ dài bằng 1.

Độ phức tạp trung bình của thuật toán là $O(NlogN)$, tuy nhiên trường hợp tệ nhất có thể lên tới $O(N^2)$.

Implement của Quicksort:

int pivot(int *a, int l, int r)
{
	int pivot = a[r];
	int left = l;
	int right = r - 1;
	while(true)
	{
		while(left <= right && a[left] < pivot) left++;
		while(right >= left && a[right] > pivot) right--;
		if (left >= right) break;
		std::swap(a[left], a[right]);
		left++;
		right--;
	}
	std::swap(a[left], a[r]);
	return left;
}
void quick_sort(int *a, int l, int r)
{
	if (l >= r) return;
	int pi = pivot(a, l, r);
	quick_sort(a, l, pi - 1);
	quick_sort(a, pi + 1, r);
}
int main()
{
	int a[5] = {5, 4, 2, 3, 1};
	quick_sort(a, 0, 4);
	for (int i = 0; i < 5; i++)
	{
		std::cout << a[i] << ' ';
	}
	std::cout << '\n';
}

Ứng dụng của thuật toán

• Trong lập trình thi đấu, Quick sort từng khá được ưa chuộng, bây giờ chủ yếu là được sử dụng trong C (hàm qsort).
• Trong thực tế, bởi vì đây là thuật toán có tốc độ chạy trung bình nhanh nhất, nó được sử dụng rộng rãi trong các hệ thống tìm kiếm trên web, khi một phương pháp với độ phức tạp ổn định là không cần thiết. Quick sort tỏ ra thân thiện và hữu dụng với bộ nhớ cache của các hệ thống khi thực hiện biến đổi ngay trên mảng gốc.

Tuy nhiên vẫn còn những thuật toán sắp xếp khác nhanh và hữu dụng hơn, mình xin được đề cập đến ở một ngày khác.

Chúc bạn thành công.