[Sort] 퀵 정렬
Sort Algorithm
04. 퀵 정렬 (Quick Sort)
대표적인 ‘분할 정복’ 알고리즘으로, 평균 속도가 빠른 정렬 방식이다.
특정한 기준 값을 기준으로, 큰 수와 작은 수를 찾아 서로 교환한 뒤, 배열을 반으로 나누어 처리하는 방식으로 수행된다.
퀵 정렬에서 기준 값을 피벗(Pivot) 이라 표현한다. 보통 0번째 index의 값을 처음 피벗 값으로 설정하고 비교한다.
/* 다음 배열을 오름차순으로 정렬하세요 */
4 9 2 5 7 10 1 3 6 8
현재 배열에서 가장 앞에 있는 값인 4를 먼저 피벗 값으로 설정한다.
피벗 값을 기준으로 우측에 있는 배열에 대해 연산을 수행하는데,
=> 으로 이동할 때는 피벗 값보다 큰 값을 찾고
<= 으로 이동할 때는 피벗 값보다 작은 값을 찾는다.
[4] 9 2 5 7 10 1 3 6 8
[4] 3 2 5 7 10 1 9 6 8
첫 번째 비교에서는 큰 값 9와 작은 값 3이 선택되었다. 두 값의 자리를 swap 해주었다.
[4] 3 2 5 7 10 1 9 6 8
[4] 3 2 1 7 10 5 9 6 8
두 번째 비교에서는 큰 값 5와 작은 값 1이 선택되었다. 두 값의 자리를 swap 해주었다.
[4] 3 2 1 7 10 5 9 6 8
1 3 2 4 7 10 5 9 6 8
세 번째 비교에서는 큰 값 7과 작은값 1이 선택된다. 이 때 큰 값과 작은 값을 찾으면서 엇갈렸다고 표현하는데, 이럴 경우 선택된 작은 값과 피벗 값을 swap 해준다. 그리고 4는 정렬이 완료되었다. 4를 기준으로 배열이 두 개로 나뉜 것이며, 좌측에는 작은 수, 우측에는 큰 수가 위치하게 된다.
[1] 3 2 4 [7] 10 5 9 6 8
[1] 2 3 4 [7] 6 5 9 10 8
위 과정을 나뉜 배열에 모두 적용하여 반복 수행하면 된다. 우측 배열에서는 1이 피벗 테이블, 좌측 배열에서는 7이 피벗 테이블이 되어 연산을 수행한다.
[1] 2 3 4 [7] 6 5 9 10 8
1 2 3 4 5 6 7 9 10 8
1 [2] 3 4 [5] 6 7 [9] 10 8
1 2 3 4 5 6 7 [9] 8 10
1 2 3 4 5 6 7 [9] 8 10
1 2 3 4 5 6 7 8 9 10
1 2 [3] 4 5 [6] 7 [8] 9 [10]
1 2 3 4 5 6 7 8 9 10
Quick Sort Process Successful !
이렇게 퀵 정렬이 완료되었다.
Source code
#include <stdio.h>
int number = 10;
int data[10] = {4, 9, 2, 5, 7, 10, 1, 3, 6, 8};
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 {
temp = data[j];
data[j] = data[i];
data[i] = temp;
}
// 함수의 재귀적 호출을 통해 정렬을 반복 수행 해준다.
quickSort(data, start, j-1);
quickSort(data, j+1, end);
}
}
int main(void) {
int i;
quickSort(data, 0, number-1);
for (i=0; i<number; i++) {
printf("%d ", data[i]);
}
}
시간 복잡도
퀵 정렬의 평균 시간 복잡도 = O(N*logN)
<logN>
2 ^ 10 = 1,000
2 ^ 20 = 1,000,000
logN, N이 1,000,000일 때 => 20
<N*N>
1 2 3 4 5 6 7 8 9 10
N ^ 2 = 10 * 10 = 100
<배열을 둘로 나눴을 때>
1 2 3 4 5 => 5 * 5 = 25
6 7 8 9 10 => 5 * 5 = 25
N*N과 비교했을 때, N*상수 와 같으므로, 굉장히 빠른 편에 속한다.
퀵정렬의 최악 시간 복잡도 = O(N^N)
/* 다음 배열을 오름차순으로 정렬하세요 */
1 2 3 4 5 6 7 8 9 10
위의 경우, 분할 정복을 수행하지 못하고 매번 피벗 값 하나씩만 정렬이 확정되기 때문에, 최악의 경우 다른 정렬 알고리즘 보다도 더 비효율적인 경우가 발생할 수 있다.
하지만 일반적으로는 가장 빠른 알고리즘이다.
