알고리즘 수업에서 처음으로 이게 뭐지 싶던 알고리즘이 퀵 정렬이었다. 정렬 파트를 공부하는 중이므로 이 부분도 다시 정리해 보려 한다.
1. Quick Sort란?
퀵 정렬이란 단계마다 pivot을 설정하여 해당 피봇보다 작은 값과 큰 값을 찾아 서로 비교한 뒤 교차되는 지점에서 피봇과 작은 값을 바꾸어 pivot이 올바른 위치에 갈 수 있도록 정렬하는 알고리즘이다.
다음 그림은 퀵 정렬 알고리즘의 이해를 돕기 위한 자료이다.
그림에서 볼 수 있듯이 퀵 정렬은 다음과 같은 방식으로 진행된다.
1. 배열에서 하나의 pivot을 선택한다.(현재는 배열의 맨 왼쪽을 피봇으로 설정)
2. 두 개의 포인터(왼쪽 l, 오른쪽 r)를 설정하여 pivot보다 큰 값은 오른쪽으로 작은 값은 왼쪽으로 이동시킨다.
3. 포인터가 교차되면 pivot과 작은 값의 위치를 교환하여 pivot을 정렬된 위치로 이동시킨다.
4. pivot을 기준으로 왼쪽과 오른쪽 배열을 나누어 재귀적으로 퀵 정렬을 반복한다.
이 과정을 거치면 전체 배열이 정렬된다.
2. 코드
#include <bits/stdc++.h>
using namespace std;
int n = 11;
int arr[1000002] = {3, 7, 12, 21, 4, -6, 5, -8, -2 ,0, 11};
void quick_sort(int st, int en)
{
if(st+1 >= en) return;
int pivot = arr[st];
int l = st+1;
int r = en-1;
while(1)
{
while(l <= r && arr[l] <= pivot) l++;
while(l <= r && arr[r] >= pivot) r--;
if(l >= r) break;
swap(arr[l], arr[r]);
}
swap(arr[r], arr[st]);
quick_sort(st, r);
quick_sort(r+1, en);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
quick_sort(0,n);
for(int i=0; i<n; i++) cout << arr[i] << ' ';
return 0;
}
// 출력 결과
// -8 -6 -2 0 3 4 5 7 11 12 21 3. 특징
1) 시간 복잡도
Quick Sort의 평균적인 시간 복잡도는 O(NlogN)이다. 일반적으로 다른 정렬 알고리즘보다 빠른 속도를 보인다. 특히 평균적인 경우에서 Merge Sort보다 빠른 성능을 보이며 추가적인 메모리 공간을 사용하지 않기 때문에 실무에서도 많이 활용된다.
다만, 이미 정렬된 배열을 기준으로 진행한다면 각 원소가 모든 원소를 탐색하고 다음 피봇으로 설정하기 때문에 최악의 경우 O(N^2)의 시간 복잡도를 가질 수 있다.
2) 불안정 정렬(Unstable Sort)
퀵 정렬은 같은 값의 원소가 입력 순서를 유지하지 않을 수 있으므로 불안정 정렬에 속한다. 즉 동일한 값을 가지는 요소들의 상대적인 순서가 보장되지 않는다.
3) 공간 복잡도
퀵 정렬은 추가적인 메모리를 요구하지 않기 때문에 제자리 정렬(In-place sort)이라고도 불린다. 하지만 재귀 호출을 사용하기 때문에 최악의 경우에는 O(N)의 스택 메모리를 사용할 수 있다.
4. 마무리
퀵 정렬은 일반적으로 가장 빠른 정렬 알고리즘 중 하나이며 실무에서도 많이 활용된다. 다만, 최악의 경우 O(N²)이 될 수 있는 점을 고려하여 랜덤 피봇 선택을 적용하는 것이 일반적이다. 이를 통해 안정적인 O(NlogN) 성능을 유지할 수 있다.
코딩테스트를 준비하는것 이라면 정렬을 구현할 때 가급적으로 퀵 정렬을 구현하기보단 Merge Sort가 안정적이라고 볼 수 있다.
Reference
[실전 알고리즘] 0x0E강 정렬I - BaaaaaaaarkingDog
