평균 시간복잡도가 O(nlogn)을 자랑하는 ‘퀵 정렬’을 알아 봅시다!
퀵 정렬의 아이디어 자체는 간단합니다.
아래 세 가지만 기억하면 됩니다!
- 리스트에서 원소 하나를 고른다. 이것을 ‘피봇’이라고 한다.
- ‘피봇’보다 작은 것과 큰 것으로 분할한다. (작은 것은 왼쪽, 큰 것은 오른쪽)
- 분할된 두 개의 작은 리스트는 재귀적으로 정렬한다.
위 로직을 이용해서 알고리즘을 소개하겠습니다!
피봇을 선정한 후 분할하는 알고리즘: Partition
임의로 피봇을 선정했을 때, 배열의 중간 값(Median)이 선정된다면 O(nlogn)을 만족하지만 한 번에 Median이 선정된다는 보장은 없습니다.
그렇다고 Median을 구하는 알고리즘을 추가하면 O(nlogn)을 만족하지 않으니까
‘피봇’은 그냥 배열의 마지막 원소로 선정합니다.
이제 아래 알고리즘대로 실행하면 ‘피봇’보다 작은 원소들은 왼쪽, 큰 원소들은 오른쪽에 위치하게 됩니다!
p는 피봇의 인덱스이고 i,b는 피봇과 값을 비교하기 위한 인덱스 변수(초기값 0)입니다.
(i = p 일 때까지 반복한다) {
If) list[i] <= list[p]
-> list[i]와 list[b]를 교환한다.
-> i와 b에 1을 더한다.
if) list[i] > list [p]
-> i에 1을 더한다.
if) i = p
-> list[b]와 list[p]를 교환힌다.
-> p를 b값으로 업데이트한다.
}
배열 [4,5,6,1,2,3]에서 피봇 3을 선정 후 Partition을 하는 모습입니다!
재귀적으로 정렬하는 알고리즘: quicksort
위의 Partition 예시의 결과는 한 번에 정렬이 끝난 모습이지만
대부분 오른쪽 리스트와 왼쪽 리스트는 정렬돼있지 않습니다.
따라서 오른쪽 리스트와 왼쪽 리스트를 Partition함수를 이용해서 다시 정렬해야 됩니다.
다시 정렬하는 과정을 반복하다 보니 순환 구조가 적합합니다!
quicksort(list,start,end){
if(end-start <1) // 베이스 케이스이자 종료 조건
return ;
p= partition(list,start,end)
quicksort(list,start,p-1) // 오른쪽 부분 정렬
quicksort(list,p+1,end) // 왼쪽 부분 정렬
}
start와 end는 각각 0, length-1이 됩니다. (length:부분 리스트의 크기)
만약 list의 길이가 1이면 정렬할 필요가 없습니다. 이 때는 end-start가 0이 되서 퀵 정렬 함수를 마칩니다.
이렇게 문제가 충분히 작아서 바로 풀 수 있는 케이스를 ‘베이스 케이스’라고 합니다.
이러한 ‘베이스 케이스’가 있어서 재귀 함수를 종료할 수 있습니다!
지금까지 설명한 내용을 C언어로 나타내겠습니다.
퀵 정렬 및 테스트 코드 (C언어)
#include <stdio.h>
// 배열의 두 요소의 위치를 바꿔주는 함수
void swap_elements(int* list, int index1, int index2) {
int temp = list[index1];
list[index1] = list[index2];
list[index2] = temp;
}
// 퀵 정렬에서 사용되는 partition 함수
int partition(int* list, int start, int end) {
// 인덱스로 사용해서 리스트 값 확인, 이 변수들은 피봇과 값을 비교하기 위해 필요함
int i, b;
i = b = start;
// 피봇의 인덱스
int p=end; // -> 피봇은 배열의 마지막 요소의 값
// 범위 안의 모든 값을 볼 때까지 반복
while (i < p) {
// list[i]가 피봇보다 작거나 같으면 list[i]와 list[b]바꾸고 i와 b는 + 1
if (list[i] <= list[p]) {
swap_elements(list, i, b);
b += 1;
}
// 그렇지 않으면 i만 + 1
i += 1;
}
// i = p가 되서 위 내용을 모두 마침
swap_elements(list, b, p);
p = b;
//피봇의 최종 인덱스는 리턴
return p;
}
// 퀵 정렬
void quicksort(int* list, int start, int end) {
/*
< 베이스 케이스: 문제가 충분히 작아서 바로 풀 수 있을 때 >
- 원소 한 개 들어와서 start = end->정렬할 필요 x
*/
if (end - start < 1)
return ;
int p = partition(list, start, end);
quicksort(list, start, p - 1); // 피봇의 왼쪽 부분 정렬
quicksort(list, p + 1, end); // 피봇의 오른쪽 부분 정렬
}
int main() {
int list[16] = { 2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4 };
for (int i = 0; i < 16; i++) // 정렬 전
printf("%d ", list[i]);
printf("\n");
quicksort(list, 0, 15); // 정렬
for (int i = 0; i < 16; i++) // 정렬 후
printf("%d ", list[i]);
return 0;
}
마지막으로 퀵 정렬을 이용해서 간단하게 시간 복잡도를 알아 봅시다!
중앙값이 피봇으로 선정되면 T(n)=2*T(n/2)+O(n)형태가 된다. -> O(nlogn)이 된다. <평균의 경우>
[오른쪽 Part와 왼쪽 Part를 나눠서 처리하는 분할정복법]
최솟값이나 최댓값이 피봇으로 선정되면 T(n)=T(n-1)+o(n)형태가 된다. -> O(n^2)이 된다. <최악의 경우>
[오른쪽 Part 혹은 왼쪽 Part만 처리]