30/09/2018, 16:12

[Wiki] Sort cơ bản 3 - Quick Sort - Sắp xếp nhanh

vi.wikipedia.org

Sắp xếp nhanh

Sắp xếp nhanh (Quicksort), còn được gọi là sắp xếp kiểu phân chia (part sort) là một thuật toán sắp xếp phát triển bởi C.A.R. Hoarec sắp thành hai danh sách con. Khác với sắp xếp trộn, chia danh sách cần sắp xếp a [ 1.. n ] {displaystyle a[1..n]} 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 ...

Xem video về Quick Sort ở đây

Đây là code

#include <iostream>
using namespace std;

void swap(int* a,int* b)	{
	
	int temp = *a;
	*a = *b;
	*b = temp;
}

int partition(int* array,int left,int right)	{
	
	int node = array[right];
	int L = left;
	
	for(int i = left; i < right; i++)	{
		
		if(array[i] <= node)	{
			
			swap(&array[i],&array[L]);
			L++;
		}
	}
	swap(&array[L],&array[right]);
	
	return L;
}

void quick_sort(int* array,int left,int right)	{
	
	if(left < right)	{
		
		int P = partition(array,left,right);
		quick_sort(array,left,P-1);
		quick_sort(array,P+1,right);
	}
	
}

int main() {
	int array[] = { 9,8,7,6,5,4,3,2,1 };
	int n = sizeof(array)/sizeof(array[0]);
	
	quick_sort(array,0,n-1);
	
	cout << n << endl;
	
	for(int i = 0; i < n; i++)	
		cout << array[i] << " ";
	
	return 0;
}

Độ phức tạp:

Best case: O(n log n)
Worst case: O(n^2)
Average: O(n log n)

Nguyễn Minh Dũng viết 18:27 ngày 30/09/2018

@minh_vu_03 có mã giả của bài này không? Post lên cho mọi người xem luôn.

viết 18:22 ngày 30/09/2018

Mã giả của quick sort mọi người xem ở cái video em mới đổi lại ở trên.

int partition(int* array,int left,int right)	{
	
	int node = array[right];
	int L = left;
	
	for(int i = left; i < right; i++)	{
		
		if(array[i] <= node)	{
			
			swap(&array[i],&array[L]);
			L++;
		}
	}
	swap(&array[L],&array[right]);
	
	return L;
}

Quick sort quan trọng ở phần phân vùng (partition) nên em giải thích ý tưởng của nó vậy (Cái này không phải ý tưởng của em)

Chọn pivot là phần tử cuối cùng trong mảng con (array[left] … array[right) để so sánh.
Đặt L là chỉ số các phần tử nhỏ hơn pivot. Khởi tạo cho nó là left.
for(i <— left to right-1)
- Nếu array[i] <= phần tử cuối cùng, swap với A[L] (đưa nó qua phía bên trái mảng con). Tăng L lên 1 đơn vị.
- Như thế thì những phần tử nằm sau chỉ số L (không tính pivot (array[right]) thì sẽ lớn hơn pivot) sẽ lớn hơn pivot. Nghĩa là lúc này ta hoán vị phần tử ngay sau chỉ số L với phần tử cuối cùng (pivot) thì sẽ tách mảng con ra thành 2 phần, phần trước pivot nhỏ hơn hoặc bằng pivot, phần sau pivot lớn hơn pivot.

Trả về chỉ số L để dùng trong việc đệ quy quick sort.

Mọi người có thể dùng cách chọn pivot là array[(left+right)/2] cũng được nhưng dùng mấy cái vòng while như người ta thường làm rắc rối hơn.

Thực tế khắc nghiệt viết 18:19 ngày 30/09/2018