Quick Sort (đôi khi được gọi là partition-exchange sort hiểu đại khái là sắp xếp phân vùng và chuyển đổi) 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ự. Là một thuật toán "nâng cấp" của Merge sort.
Data Structure & Algorithm Trung Nguyễn 2016-10-08 15:10:06

Giới thiệu

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 Merge Sort, các bạn nên nắm rõ thuật toán Merge Sort trước khi tiếp cận thuật toán này.

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 của chúng ta thành hai mảng con nhỏ hơn: mảng có phần tử nhỏ và mảng có phần tử lớn. Sau đó Quick sort có thể sort các mảng con này bằng phương pháp đệ quy. Các bước ý tưởng của Quick sort là:

  1. Chọn một phần tử để so sánh, tôi gọi đây là phần tử Key hoặc Pivot tùy vào mỗi người, từ trong mảng đầu tiên của chúng ta.
  2. Sau đó phân vùng và sort mảng con của sau phân vùng của chúng ta làm sao cho các phần tử lớn hơn 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).

Quicksort

Hiện thực

// 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
		// Reference Giải Thuật Đệ Quy :: STDIO.VN
		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).

Code C++ của các giải thuật sắp xếp khác

Download code C++ của các giải thuật sắp xếp khác tại đây.

Tham khảo

https://en.wikipedia.org/wiki/Quicksort - 10/6/2016