Nagie's DevStory
[ALGORITHM] 20. 퀵 정렬 구현하기 본문
728x90
퀵 정렬(Quick Sort)은 토니 호어가 1960년에 개발한 평균적으로 빠른 속도를 가지는 정렬 알고리즘으로
분할 정복(Divide and Conquer) 방법을 사용하며, 배열을 피벗 기준으로 작은 요소들과 큰 요소들로 나누어 각각을 정렬 후
최종적으로 정렬된 부분을 합치는 방식을 사용한다.
template<typename T>
int partition(std::vector<T>& data, int left, int right) {
T pivot = data[left];
int i = left + 1;
int j = right;
while (true) {
while (data[i] <= pivot && i <= right) {
i++;
}
while (data[j] > pivot && j > left) {
j--;
}
if (i < j) {
std::swap(data[i], data[j]);
} else {
break;
}
}
std::swap(data[left], data[j]);
return j;
}
template<typename T>
void quick_sort(std::vector<T>& data, int left, int right) {
if (left < right) {
int p = partition(data, left, right);
quick_sort(data, left, p - 1);
quick_sort(data, p + 1, right);
}
}
특징
1. 불안정 정렬(Unstable Sort) : 동일한 키 값을 가진 원소의 상대적인 순서가 정렬 전후에 유지되지 않을 수 있다.
2. 원소의 이동이 적음 : 일반적으로 다른 O(n²) 알고리즘들 보다 원소의 이동이 적기 때문에 상대적으로 빠르다.
3. 평균 시간 복잡도가 좋음 : 평균적으로 O(n log n)의 시간 복잡도를 가지며, 대다수의 상황에서 좋은 성능을 보여준다.
장점
1. 빠른 속도 : 평균적으로 다른 정렬 알고리즘들보다 빠른 속도를 가진다.
2. 메모리를 효율적으로 활용 : 추가적인 메모리를 필요로하지 않거나 상대적으로 적은 메모리를 사용하므로 효율적이다.
3. 캐시 지역성을 활용 : 데이터를 작은 블록 단위로 정렬하므로 캐시 지역성을 활용하여 더 빠른 속도를 가질 수 있다.
단점
1. 최악의 경우 시간 복잡도가 높음 : 이미 정렬된 배열이나 역순으로 정렬된 배열과 같이 최악의 상황에는
O(n²)의 시간 복잡도를 가지나 요즘은 최적화 기법을 사용하여 O(n²) 시간 복잡도를 가지는 경우가 잘 없음
2. 불안정성 : 동일한 키 값을 가진 원소의 순서가 유지되지 않을 수 있다.
728x90
Comments