[자료구조] 퀵 정렬 (quick sort)

퀵 정렬이란?

퀵 정렬은 합병 정렬과 동일하게 분할 정복 알고리즘을 사용합니다. 차이점이 존재한다면, 퀵 정렬은 리스트를 비균등하게 분할합니다.

 

작동 방식

작동 방식에 앞서, 퀵 정렬에는 피벗(pivot)이라는 요소가 존재합니다.

피벗이란, 뜻 그대로 중심점이라는 뜻입니다. 퀵 정렬은 중심축을 기준으로 왼쪽 리스트와 오른쪽 리스트로 나뉩니다. 따라서 피벗이라는 요소가 존재하고 반드시 알고 있어야 합니다. 피벗을 설정할 때는 리스트의 첫 번째 요소로 하던 가운데 요소로 하던 상관 없습니다. 여기에서는 첫 번째 요소로 하겠다는 가정으로 진행하겠습니다.

 

리스트 안에 있는 한 요소를 피벗으로 선택하고, 피벗을 기준으로 작은 요소들은 왼쪽으로 옮기고 큰 요소들은 오른쪽으로 옮깁니다. 다 했다면 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 정렬이 불가능할 때까지 반복합니다.

 

 

퀵 정렬 구현

퀵 정렬의 핵심은 아무거나 정해서 작은건 왼쪽에, 큰거는 오른쪽에입니다.

 

과정은 아래와 같습니다.

1. 리스트 안에 있는 한 요소를 피벗으로 선택함
2. 피벗보다 작은 요소들은 피벗의 왼쪽으로 / 피벗보다 큰 요소들은 피벗의 오른쪽으로 옮겨짐
   • left 포인터(리스트의 두 번째 요소)는 증가시키면서 피벗과 비교. 피벗보다 크면 멈춤
   • right 포인터(리스트의 마지막 요소)는 감소시키면서 피벗과 비교. 피벗보다 작으면 멈춤
   • left 포인터가 right 포인터보다 왼쪽에 있다면, 교환.
3. left 포인터가 right 포인터보다 왼쪽에 있을 때까지 2번 반복
4. right 포인터 오른쪽에 바로 left 포인터가 있을 때 그 곳에 pivot 이동
5. 피벗 왼쪽 리스트와 피벗 오른쪽 리스트를 대상으로 퀵 정렬

 

코드로 구현하면 아래와 같습니다.

int partition(int list[], int left, int right) {
	int pivot, temp;
	int low = left, high = right + 1;

	pivot = list[left];

	while(low < high) {
		while(list[low] < pivot) low++;
		while(list[high] > pivot) high--;
		if(low < high) SWAP(list[low], list[high], temp);
	}

	SWAP (list[left], list[high], temp);
	return high;
}

void quick_sort(int list[], int left, int right) {
	if (left < right) {
		int pivot = partition(list, left, right);
		quick_sort(list, left, pivot - 1);
		quick_sort(list, pivot + 1, right);
	}
}

 

퀵 정렬의 시간복잡도

퀵 정렬은 평균 $O(n \space log \space n)$의 복잡도를 가집니다. 최선은 $O(log \space n)$, 최악은 $O(n^2)$입니다.

 

평균 시간복잡도 도출 방법

partition의 개수를 낱개가 될 때까지 나누게 됩니다. 그렇게 되면 요소의 개수 $n$개 만큼의 비교하는 시간이 소요됩니다.

한편, partition을 나눌 때마다 데이터의 개수가 반으로 줄게 되므로 $log \space n$의 시간이 소요됩니다. 따라서 시간복잡도가 $O(n \space log \space n)$가 되는 것입니다.

 

최악 시간복잡도 도출 방법

최악의 상황은 partition을 나누는데 매 번 선택한 pivot이 하필 항상 제일 작거나 제일 클 때입니다. 그렇게 되면 리스트의 한 쪽이 텅 비는 상황이 생기게 됩니다. 이렇게 되면 데이터의 개수가 줄어드는 데 소요되는 시간이 $log \space n$이 아니라 $n$의 시간이 소요됩니다. 따라서 복잡도가 $O(n^2)$가 되는 것입니다.

 

 

[자료구조] 선택 정렬 (selection sort)

[자료구조] 삽입 정렬 (insertion sort)

[자료구조] 버블 정렬 (bubble sort)

[자료구조] 셸 정렬 (shell sort)

[자료구조] 합병 정렬 (merge sort)

[자료구조] 힙 정렬 (heap sort)

[자료구조] 기수 정렬 (radix sort)