정렬 (6) - 퀵 정렬 (Quick Sort)

1. 알고리즘 개요

• Quick Sort : Pivot을 기준으로 절반으로 쪼개고 왼쪽은 Pivot보다 작은 값, 오른쪽은 큰 값이 오게 함.
• Partition : L에서 Pivot보다 큰 값을 찾고, R에서 작은 값을 찾아서 맞바꾸고 L과 R을 한칸씩 이동
• 시간복잡도 : $O(n logn)$, 최선의 경우에 $O(nlogn)$이고, 최악의 경우(피봇편향) $O(n^2)$의 성능을 보인다.
• 특징 : Pivot이 편향되었는지 중간 값인지에 따라 성능이 좌우된다. 따라서 Pivot을 선정하는 방법이 중요하다.

 

[그림[ 퀵정렬 애니메이션

 

2. 소스코드

#include<stdio.h>

int swap(int *arr, int l, int r){
	int temp = arr[l];
	arr[l] = arr[r];
	arr[r] = temp;
}

int partition(int arr[], int l, int r){
	int center = (l + r) / 2;
	int pivot = arr[center];
	
	while(l <= r){
		while(arr[l] < pivot) l++;
		while(arr[r] > pivot) r--;
		
		if(l <= r){
			swap(arr, l, r);
			l++; r--;
		}
	}
	return l;
}

void quick_sort(int *arr, int l, int r){
	if(l < r){
		int p = partition(arr, l, r);
		
		quick_sort(arr, l, p-1);
		quick_sort(arr, p, r);
	}
}

void quick_sort(int *arr, int size){
	quick_sort(arr, 0, size-1);
}

int main(){
	int arr[] = {2, 4, 1, 3, 5, 7, 6, 9, 8};
	int size = sizeof(arr)/sizeof(arr[0]);
	quick_sort(arr, size);
	
	for(int i = 0 ; i < size ; i++){
		printf("%d ", arr[i]);
	}
	
	return 0;
}

 

3. Reference