퀵 정렬 알고리즘 (Quick Sort)
퀵 정렬은 특정 데이터를 기준으로 큰 데이터와 작은 데이터를 서로 교환한 후 배열을 두 집합으로 나누는 방식의 알고리즘입니다. 기준이 되는 특정한 데이터, 즉 기준점을 피벗(Pivot)이라고 하며 일반적으로 첫번째 원소를 먼저 피벗으로 지정합니다.
퀵 정렬 알고리즘은 한번 과정을 이해하면 어렵지 않은 알고리즘이기에 정렬 과정을 자세히 풀이하겠습니다.
4 9 1 6 11 10 3 15 2 13
위와 같은 수가 있을 때 수들을 오름차순하는 퀵 정렬을 해보겠습니다.
먼저 피벗 값은 4로 시작하여 4를 기준으로 왼쪽부터 큰 값을 찾고 오른쪽 부터 작은 값을 찾는 과정을 수행합니다.
4 9 1 6 11 10 3 15 2 13
4 2 1 6 11 10 3 15 9 13
큰 값은 9, 작은 값은 2가 되고 큰 값과 작은 값의 위치를 교환합니다.
4 2 1 6 11 10 3 15 9 13
4 2 1 3 11 10 6 15 9 13
피벗 값은 유지한 채 다시 왼쪽에서 큰 값(6), 오른쪽에서 작은 값(3)을 찾고 위치를 교환합니다.
4 2 1 3 11 10 6 15 9 13
3 2 1 4 11 10 6 15 9 13
피벗 값은 유지한 채 다시 왼쪽에서 큰 값(11), 오른쪽에서 작은 값(3)을 찾습니다. 그런데 큰 값의 인덱스가 작은 값의 인덱스보다 더 높은, 엇갈린 상황이 되면 둘 중 작은 값을 피벗 값과 위치를 교환합니다.
이렇게 되면 교환된 4는 정렬이 확정되고 4의 왼쪽은 4보다 작은 수들, 오른쪽은 4보다 큰 수들이 됩니다.
3 2 1 4 11 10 6 15 9 13
이제 4의 왼쪽 집합과 오른쪽 집합에서 각각 첫번째 원소를 피벗으로 지정하고 두 집합의 퀵 정렬을 동시에 수행합니다.
1 2 3 4 11 10 6 15 9 13
1 2 3 4 11 10 6 15 9 13
왼쪽 집합에서, 3을 기준으로 큰 값은 존재하지 않으므로 마지막 부분(1의 다음 인덱스)을 가리키게 되며 작은 값은 1이므로 엇갈린 상황이 되어 작은 값인 1과 피벗 값의 위치를 교환하고 교환된 3의 정렬을 확정합니다.
1 2 3 4 11 10 6 15 9 13
1 2 3 4 11 10 6 15 9 13
다시 피벗 1을 기준으로 큰 값은 존재하지만 작은 값이 존재하지 않아 이 경우 자기 자신이 작은 값이 됩니다. 엇갈린 상황이 되어 작은 값인 1이 자기자신과 교환되고 정렬을 확정합니다. 2는 원소가 하나이므로 그대로 정렬을 확정합니다.
1 2 3 4 11 10 6 15 9 13
1 2 3 4 11 10 6 9 15 13
오른쪽 집합에서, 11을 기준으로 큰 값 15와 작은 값 9의 위치를 교환합니다.
1 2 3 4 11 10 6 9 15 13
1 2 3 4 9 10 6 11 15 13
큰 값은 15, 작은 값은 9가 되므로 엇갈린 상황이 되어 작은 값과 피벗 값을 교환하고 11의 정렬을 확정합니다.
1 2 3 4 9 10 6 11 15 13
1 2 3 4 9 6 10 11 15 13
1 2 3 4 6 9 10 11 15 13
1 2 3 4 6 9 10 11 15 13
9를 기준으로 큰 값은 10, 작은 값은 6이되어 위치를 교환합니다.
9를 기준으로 큰 값은 10, 작은 값은 6이되어 엇갈린 상황이 되므로 교환된 9의 정렬을 확정합니다.
원소가 하나인 6과 10은 그대로 정렬이 확정됩니다.
1 2 3 4 6 9 10 11 15 13
1 2 3 4 6 9 10 11 13 15
마지막으로 15를 기준으로 큰 값은 13의 다음 인덱스를 가리키고 작은 값은 13이 되어 엇갈린 상황이 되므로 두 수를 교환하고 교환된 15의 정렬을 확정합니다. 이후 원소가 하나인 13도 정렬이 확정됩니다.
알고리즘 구현
// Algorithm Analysis
// 퀵 정렬(Quick Sort) : 특정 값을 기준으로 큰 데이터와 작은 데이터를 서로 교환한 후 배열을 두 집합으로 나눈다.
#include <stdio.h>
void quickSort(int* data, int start, int end) {
if (start >= end) {
return;
}
int pivot = start;
int i = start + 1;
int j = end;
int temp;
while (i <= j) { // 엇갈릴 때까지
while (i <= end && data[i] <= data[pivot]) // 피벗 보다 큰 값을 만날 때까지
i++;
while (j > start && data[j] >= data[pivot]) // 피벗 보다 작은 값을 만날 때까지
j--;
if (i > j) { // 엇갈리면 피벗과 교체
temp = data[j];
data[j] = data[pivot];
data[pivot] = temp;
}
else { // 엇갈리지 않으면
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
quickSort(data, start, j - 1);
quickSort(data, j + 1, end);
}
int main() {
int arr[10] = { 4, 9, 1, 6, 11, 10, 3, 15, 2, 13 };
quickSort(arr, 0, 9);
for (int i = 0; i < 10; i++)
printf("%d ", arr[i]);
return 0;
}
평균 시간 복잡도 : O(N*logN)
이름에서 부터 나타나듯이 퀵 정렬은 대표적인 분할 정복 알고리즘으로써 평균 시간 복잡도는 O(N*logN)으로 매우 빠른 알고리즘 중 하나이지만 어디까지나 평균 값이므로 항상 동일한 복잡도가 유지되는 것은 아닙니다.
최악 시간 복잡도 : O(N^2)
퀵 정렬 알고리즘이 매우 비효율적으로 작용하는 경우는 바로 거의 혹은 이미 정렬된 데이터에 대한 정렬입니다.
1 2 3 4 6 9 10 11 13 15
위와 같이 이미 정렬된 데이터의 경우 퀵 정렬을 사용하면 시간 복잡도가 O(N^2)까지 증가하게 되어 분할 정복의 이점을 사용하지 못하게됩니다.
따라서, 퀵 정렬은 가장 빠른 알고리즘 중 하나이지만 위와 같이 거의 혹은 이미 정렬된 배열의 경우에는 퀵 정렬보다 삽입 정렬을 사용하는 것이 더 빠른 연산 속도를 보이게 되므로 모든 상황에서 항상 퀵 정렬이 가장 효율적인 것은 아닙니다.
* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.