[알고리즘] 퀵 정렬(quick sort) 란 - travelbeeee

안녕하세요, 여행벌입니다.

오늘은 퀵정렬(Quick sort)에 대해서 포스팅해보겠습니다.

---

퀵 정렬의 원리

 퀵 정렬은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘입니다.

 

 퀵 정렬은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방식으로 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵 정렬하는 분할 정복 방법을 사용합니다.

 

 먼저 리스트 안에 있는 한 요소를 피벗(Pivot)으로 선택합니다. 우리는 리스트의 첫 번째 요소를 피벗으로 선택하고 퀵 정렬을 진행하겠습니다. 물론, 다른 요소를 피벗으로 선택해도 무관합니다. 그 후, 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮기고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮깁니다. 결과적으로 피벗을 중심으로 왼쪽은 피벗보다 작은 요소들로 구성된 부분 리스트, 오른쪽은 피벗보다 큰 요소들로 구성된 부분 리스트가 생깁니다. 그 후 각각 부분 리스트에 대해서 같은 과정을 반복합니다.

---

퀵 정렬 예시

( 5 3 8 4 9 1 6 2 7 ) 리스트를 퀵 정렬을 이용해 정렬해보겠습니다.

 

 처음에는 전체 리스트에 대해서 퀵 정렬을 진행합니다.

 첫 번째 요소를 피벗으로 선택하므로 피벗은 5가 되고 left 는 전체 리스트의 가장 왼쪽, right 는 전체 리스트의 가장 오른쪽을 지칭합니다.

 low 는 피벗을 제외한 리스트의 왼쪽부터 피벗보다 큰 값을 찾아나가고, high 는 리스트의 오른쪽부터 피벗보다 작은 값을 찾아나갑니다.

(2) low 는 피벗 5보다 큰 8에서 멈추고 high 는 피벗 5보다 작은 2에서 멈춥니다. 그 후 둘을 SWAP 합니다.

(3) low 는 피벗 5보다 큰 9에서 멈추고 high 는 피벗 5보다 작은 1에서 멈춥니다. 그 후 둘을 SWAP 합니다.

(4) low 는 피벗 5보다 큰 9에서 멈추고 high 는 피벗 5보다 작은 1에서 멈춥니다. 하지만, low 와 high 가 뒤바뀐 것을 확인할 수 있습니다. 따라서, 더 이상 퀵 정렬을 진행하지 않고 high 와 pivot 을 SWAP 합니다.

(5) 피벗을 기준으로 왼쪽 리스트에는 피벗보다 작은 값, 오른쪽 리스트에는 피벗보다 큰 값들이 모여있는 것을 확인할 수 있습니다.

 

이제 두 개의 부분 리스트 [ 1 3 2 4 ] 와 [ 9 6 8 7 ] 에 대해서 각각 퀵 정렬을 진행합니다.

왼쪽 리스트의 피벗은 1로 오른쪽 리스트의 피벗은 9로 지정합니다.

같은 작업을 진행해 최종적으로 [ 1 3 2 4 ] 리스트는 [ 1 ] / [ 3 2 4 ] 2개의 부분 리스트로 나눠지고,

[ 9 6 8 7 ] 리스트는 [ 7 6 8 ] / [ 9 ] 2개의 부분 리스트로 나눠집니다.

크기가 1인 리스트는 이미 정렬이 되어있으므로 [ 3 2 4 ] / [ 7 6 8 ] 리스트에 대해서 퀵 정렬을 진행합니다.

왼쪽 리스트의 피벗은 3으로 오른쪽 리스트의 피벗은 7로 지정합니다.

같은 작업을 진행해 최종적으로 [ 2 ] / [ 3 ] / [ 4 ] 와 [ 6 ] / [ 7 ] / [ 8 ]  6개의 부분 리스트로 나눠집니다.

모든 리스트의 크기가 1이므로 정렬이 완료됩니다.

 

퀵 정렬은 전형적인 분할 정복 기법을 활용한 정렬 방식입니다.

요약하면 퀵 정렬은 아래 그림과 같이 움직인다고 볼 수 있습니다.

---

퀵 정렬 코드

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);
	}
}

---

퀵 정렬 복잡도

퀵 정렬의 복잡도는 리스트 상태에 따라 크게 바뀝니다.

만약 퀵 정렬에서의 리스트 분할이 항상 그림과 같이 리스트의 가운데에서 이루어진다고 가정하면 n 개의 레코드를 가지는 리스트가 n / 2, n / 4 와 같이 반으로 계속 분할될 것이고, 따라서 log(n) 번 분할이 발생합니다. 또 각 분할마다 평균 n번 정도의 비교가 이루어지므로 퀵 정렬의 복잡도는 nlog(n) 이 됩니다.

 하지만 리스트가 계속 불균형하게 나누어지는 경우에는 최대 n 번의 분할이 발생하고, 각 분할마다 평균 n번 정도의 비교가 이루어지므로 퀵 정렬의 복잡도는 n^2 가 됩니다.

 그럼에도 불구하고 퀵 정렬은 평균적인 경우의 시간 복잡도가 O( nlogn ) 으로 나타나고 같은 O( nlogn ) 복잡도를 가지는 정렬 중에서도 가장 빠릅니다.

---

퀵 정렬 안정성

퀵 정렬은 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있는 불안정 정렬에 속합니다.

 [ 5-1 5-2 3 2 1 ] 를 퀵 정렬로 정렬해보겠습니다.

[ 5-1 5-2 3 2 1] → [ 1 2 3 5-2 5-1 ]

 위와 같이 퀵 정렬은 같은 값이 있는 경우에 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있습니다.

---

이상으로 퀵 정렬 포스팅을 마치겠습니다.