Sắp xếp nhanh – Quick Sort

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. Dưới đây mình sẽ hướng dẫn thế nào là điểm đánh dấu (pivot) và phân đoạn (partition).

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ố (Xem hàm partition()). 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. Dưới đây là hướng dẫn cụ thể (ở bài này mình chọn điểm đánh dấu pivot là phần tử cuối cùng của mảng):

• Đặt pivot là phần tử cuối cùng của mảng arr.
• Chúng ta bắt đầu từ phần tử trái nhất của mảng có chỉ số là low và phần tử phải nhất của dãy số có chỉ số là high – 1 (bỏ qua phần tử pivot).
• Lặp lại cho đến khi low < high mà arr[low] > pivot và arr[high] < pivot thì đổi chỗ hai phần tử low và high.
• Sau cùng, ta đổi chỗ hai phần tử low và pivot cho nhau. Khi đó, phần tử low đã đứng đúng vị trí và chia dãy số làm đôi (bên trái và bên phải).

Cài đặt

// Java program for implementation of QuickSort 
class QuickSort 
{ 
	/* This function takes last element as pivot, 
	places the pivot element at its correct 
	position in sorted array, and places all 
	smaller (smaller than pivot) to left of 
	pivot and all greater elements to right 
	of pivot */
	int partition(int arr[], int low, int high) 
	{ 
		int pivot = arr[high]; 
		int i = (low-1); // index of smaller element 
		for (int j=low; j<high; j++) 
		{ 
			// If current element is smaller than or 
			// equal to pivot 
			if (arr[j] <= pivot) 
			{ 
				i++; 

				// swap arr[i] and arr[j] 
				int temp = arr[i]; 
				arr[i] = arr[j]; 
				arr[j] = temp; 
			} 
		} 

		// swap arr[i+1] and arr[high] (or pivot) 
		int temp = arr[i+1]; 
		arr[i+1] = arr[high]; 
		arr[high] = temp; 

		return i+1; 
	} 


	/* The main function that implements QuickSort() 
	arr[] --> Array to be sorted, 
	low --> Starting index, 
	high --> Ending index */
	void sort(int arr[], int low, int high) 
	{ 
		if (low < high) 
		{ 
			/* pi is partitioning index, arr[pi] is 
			now at right place */
			int pi = partition(arr, low, high); 

			// Recursively sort elements before 
			// partition and after partition 
			sort(arr, low, pi-1); 
			sort(arr, pi+1, high); 
		} 
	} 

	/* A utility function to print array of size n */
	static void printArray(int arr[]) 
	{ 
		int n = arr.length; 
		for (int i=0; i<n; ++i) 
			System.out.print(arr[i]+" "); 
		System.out.println(); 
	} 

	// Driver program 
	public static void main(String args[]) 
	{ 
		int arr[] = {10, 7, 8, 9, 1, 5}; 
		int n = arr.length; 

		QuickSort ob = new QuickSort(); 
		ob.sort(arr, 0, n-1); 

		System.out.println("sorted array"); 
		printArray(arr); 
	} 
} 

Và kết quả là một mảng được sắp xếp hoàn chỉnh:

Sorted array:
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²)

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ữ