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

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)