퀵 정렬(Quick Sort)

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하시오. 

1 10 5 8 7 6 4 3 2 9

---

퀵 정렬

하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬한다. 

특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다.

 

퀵정렬에서는 기준값 (=피벗(Pivot))이 있는데, 보통 첫 번째 원소를 피벗 값으로 설정하고 사용한다. 

다음과 같이 1이라는 값이 먼저 피벗 값으로 설정되었다고 생각해보자. 

 

(1) 10 5 8 7 6 4 3 2 9

 

이 경우 1보다 큰 숫자를 왼쪽부터 찾고, 1보다 작은 숫자를 오른쪽부터 찾는다.

이 때 1보다 큰 숫자로는 바로 10을 찾을 수 있고, 1보다 작은 숫자는 찾지 못해서 결국 1까지 도달한다.

이 때 작은 값의 인덱스가 큰 값의 인덱스보다 작으므로 피벗 값과 작은 값의 위치를 바꾼다. 

즉. 1과 1을 교환하므로 제자리 걸음이 된다. 

 

1 10 5 8 7 6 4 3 2 9

 

따라서 위와 같이 구성되고, 이 때 피벗 값이었던 1의 왼쪽에는 1보다 작은 값이 존재, 오른쪽에는 1보다 큰 값이 존재한다. 이제 이어서 왼쪽과 오른쪽에서 퀵 정렬을 순환적으로 수행한다. 

 

1 (10) 5 8 7 6 4 3 2 9

 

이 때 왼쪽은 없으므로 무시하고, 오른쪽에서는 피벗 값으로 10이 채택된다. 

10보다 큰 값을 왼쪽부터 찾고, 10보다 작은 값을 오른쪽부터 찾는다. 

큰 값은 찾지 못하게 되며, 작은 값은 바로 9를 찾게 된다. 

이 때, 작은 값의 인덱스가 큰 값의 인덱스보다 작으므로 9와 10을 교환한다. 

 

1 9 5 8 7 6 4 3 2 10

 

따라서 위와 같이 구성되고, 이 떄 피벗 값이었던 10의 왼쪽에는 10보다 작은 값이 존재하며 오른쪽에는 10보다 큰 값이 존재한다. 이제 이어서 왼쪽과 오른쪽에서 퀵 정렬을 순환적으로 수행한다. 

 

1 (9) 5 8 7 6 4 3 2 10 

 

이 때 오른쪽은 없으므로 무시하고, 왼쪽에서는 피벗값으로 9가 채택된다. 9보다 큰 값을 왼쪽부터 찾고, 9보다 작은 값을 오른쪽에서 부터 찾는다. 큰 값으로는 10이 선택되고, 작은 값으로는 2가 선택된다. 이 때 숫자가 엇갈리기 때문에 작은 값 2가 피벗값인 9의 숫자와 바꾸게 된다. 

 

1 2 5 8 7 6 4 3 9 10 

 

 

이제 9를 기준으로 하여 9보다 작은 값은 왼쪽에 있고, 9보다 큰 값은 오른쪽에 있다. 이제 5의 왼쪽과 오른쪽에서 추가적으로 퀵 정렬 수행을 한다. 바로 다음과 같이 피벗 값이 설정된다. 

 

1 2 (5) 8 7 6 4 3 9 10 

 

1 2 3 8 7 6 4 5 9 10

 

.

.

.

 

1 2 3 4 5 6 7 8 9 10

 

이런식으로 수행하다보면 퀵 정렬이 완료된다. 

 

---

코드 및 풀이 (with. c언어)

#include <stdio.h>

int number = 10;
int data[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; 

void quickSort(int *data, int start, int end) {
	if (start >= end) { // 원소가 1개인 경우 그대로 두기 
		return; 
	}
	
	int key = start;  // 키는 첫번째 원소  
	int i = start + 1;
	int j = end;
	int temp;
	
	while(i <= j){  // 엇갈릴 때까지 반복 
		while(data[i] <= data[key]) { // 키 값보다 큰 값을 만날 때 까지 오른쪽으로 이동 
			i++; 
		}
		while(data[j] >= data[key] && j > start) { // 키 값보다 작은 값을 만날 때까지 왼쪽으로 이동 
			j--; 
		} 
		if(i > j) { // 현재 엇갈린 상태라면 키 값과 교체 
			 temp = data[j];
			 data[j] = data[key];
			 data[key] = temp; 
		} else { // 엇갈리지 않았다면 i와 j를 교체 
			temp = data[j];
			data[j] = data[i];
			data[i] = temp;
		}
	
	}
	 
	quickSort(data, start, j - 1);
	quickSort(data, j + 1, end);  //재귀함수로 퀵 정렬 수행
	
}

int main(void) {
	quickSort(data, 0, number - 1);
	for (int i = 0; i < number; i++) {
		printf("%d ", data[i]); 
	}
	
	return 0;
}

위의 소스코드를 보면 '키 값보다 작은 값을 만날 때까지' 반복하는 부분에서 j가 start보다 클 때에 한해서만 반복문이 수행되도록 처리되어 있다. 이는 항상 왼쪽에 있는 값과 피벗 값을 교환하기 때문이다. 오른쪽에 있는 값은 피벗 값과 교환되지 않으므로 처리해 줄 필요가 없다. 

 

---

실행 결과 

퀵 정렬 알고리즘은 기본적으로 N번씩 탐색하되 반으로 쪼개 들어간다는 점에서 log N을 곱한 복잡도를 가진다. 

 

퀵 정렬의 평균 시간 복잡도는 O(N*logN)이다.

하지만 퀵 정렬의 최악 시간 복잡도는 바로 O(N^2)이다. 

퀵 정렬의 최악 시간 복잡도는 O(N^2)이다.

 

---

추가 설명

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하시오. 

1 2 3 4 5 6 7 8 9 10 

 

위와 같이 이미 정렬되어 있는 경우 퀵 정렬의 시간 복잡도는 O(N^2)에 가깝다. 

반면 삽입 정렬의 경우 위 문제를 매우 빠르게 풀어낼 수 있다. 

즉, 정렬할 데이터의 특성에 따라서 적절한 정렬 알고리즘을 사용하는 것이 중요하다는 것이다.