Search…

Quick Sort

17/08/20202 min read
Giới thiệu và hướng dẫn dẫn thuật toán Quick Sort và code mẫu hiện thực Quick Sort.

Quick sort là một thuật toán sắp xếp tương đối hiệu quả, phục vụ dựa trên phương pháp để đặt các phần tử trong một mảng (array) theo thứ tự dựa trên một phần tử Key (Pivot). Là một thuật toán "nâng cấp" của thuật toán sắp xếp Merge Sort.

Thuật toán Quick Sort

Ý tưởng

Quick sort là một trong những thuật toán chia để trị, Quick sort chia một mảng lớn thành 2 mảng con nhỏ hơn:

  • Mảng có phần tử nhỏ.
  • Mảng có phần tử lớn.

Sau đó Quick sort có thể sort các mảng con bằng phương pháp đệ quy, ý tưởng của Quick sort là:

  1. Chọn một phần tử để so sánh, gọi là phần tử Key (Pivot), từ trong mảng đầu tiên.
  2. Phân vùng và sort mảng con trong phân vùng làm sao cho các phần tử lớn hơn từ phần tử Key nằm sau (bên phải) và các phần tử bé hơn phần tử Key nằm trước (bên trái). Đây được gọi là quá trình phân vùng.
  3. Cuối cùng là đệ quy sử dụng các bước trên cho các mảng với phần tử bé hơn và phân tách với các phần tử lớn hơn sau khi phân vùng.

Các cách chọn phần tử Key

  1. Chọn phần tử bên trái ngoài cùng (phần tử đầu tiên của mảng).
  2. Chọn phần tử bên phải ngoài cùng (phần tử cuối cùng của mảng).
  3. Ngẫu nhiên một phần tử (sử dụng hàm random mà ngôn ngữ lập trình cung cấp).
  4. Phần tử chính giữa của mảng (chiều dài của mảng chia đôi).
Thuật toán Quick Sort

Code mẫu Quick Sort

// Take Left (first) Index of the array and Right (last) Index of the array
void quickSort(int Data[], int l , int r)
{
	// If the first index less or equal than the last index
	if (l <= r)
	{
		// Create a Key/Pivot Element
		int key = Data[(l+r)/2];

		// Create temp Variables to loop through array
		int i = l;
		int j = r;

		while (i <= j)
		{
			while (Data[i] < key)
				i++;
			while (Data[j] > key)
				j--;

			if (i <= j)
			{
				swap(Data[i], Data[j]);
				i++;
				j--;
			}
		}

		// Recursion to the smaller partition in the array after sorted above
if (l < j) quickSort(Data, l, j); if (r > i) quickSort(Data, i, r); } }

Tốc độ của thuật toán và các trường hợp xấu nhất dựa trên cách chọn phần tử so sánh (key/pivot). Đối trường hợp xấu nhất thì thuật toán này vẫn khá nhanh với O(n2).

IO Stream

IO Stream Co., Ltd

30 Trinh Dinh Thao, Hoa Thanh ward, Tan Phu district, Ho Chi Minh city, Vietnam
+84 28 22 00 11 12
developer@iostream.co

383/1 Quang Trung, ward 10, Go Vap district, Ho Chi Minh city
Business license number: 0311563559 issued by the Department of Planning and Investment of Ho Chi Minh City on February 23, 2012

©IO Stream, 2013 - 2024