Quick Sort

퀵 정렬은 리처드 호어가 개발한 정렬 알고리즘으로 평균적으로 앞에서 다룬 Selection, Bubble, Insertion Sort 알고리즘보다 빠른 수행 속도를 자랑한다.

전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵 정렬하는 분할 정복 방법을 사용한다.

먼저, 리스트 안에 한 요소를 피벗(Pivot)으로 선택하고 피벗을 기준으로 피벗보다 작은 요소들은 피벗의 좌측, 큰 요소들은 피벅의 우측으로 옮겨서 피벗을 기준으로 2개의 부분 리스트로 분할한다. 분할된 리스트도 마찬가지로 퀵 정렬을 재귀적으로 수행한다. ( 우리는 리스트의 맨 앞 요소를 피벗으로 선택하겠다. )

코드 구현

int partition(int list[], int left, int right) {
	int pivot, temp, low, high;
	low = left;
	high = right + 1;
	pivot = list[left];
	do {
		do {
			low++;
		} while (low <= right && list[low] < pivot);
		do {
			high--;
		} while (high >= left && list[high] > pivot);
		if (low < high) { //SWAP진행.
			temp = list[low];
			list[low] = list[high];
			list[high] = temp;
		}
	} while (low < high);

	temp = list[left];
	list[left] = list[high];
	list[high] = temp;
	return high;
}

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

시간 복잡도

퀵 정렬은 평균적으로 빠른 정렬 알고리즘이다. 이는 리스트 상태에 따라 퀵 정렬의 속도가 크게 영향받기 때문이다. 피벗을 기준으로 분할할 때 아래 그림과 같이 분할 리스트들의 크기가 반으로 줄어든다면 log(n) 번 분할이 발생하고, 각 분할마다 평균 n번 정도의 비교가 이루어지므로 O ( nlog(n) ) 시간 복잡도를 가지게 된다.