C++20 반복자를 이용한 정렬 알고리즘 구현 2: 합병, 퀵, 힙
C++20 반복자를 이용한 정렬 알고리즘 구현 1: 삽입, 선택, 버블과 이어지는 글입니다.
이번에는 전에 소개한 정렬 알고리즘보다 더 빠르게 동작하는 알고리즘을 알아 볼 것입니다.
합병 정렬
출처: 위키백과
합병 정렬(Merge Sort)는 분할 정복 기법을 이용해 정렬하는 알고리즘입니다.
namespace sort {
template<std::random_access_iterator I,
std::sentinel_for<I> S,
typename Compare = std::less<>>
void merge_sort(I first, S last, Compare cmp = Compare{}) {
if (last - first > 1) {
auto middle = first + (last - first) / 2;
merge_sort(first, middle, cmp);
merge_sort(middle, last, cmp);
std::inplace_merge(first, middle, last, cmp);
}
}
} // namespace sort
합병 정렬은 구간을 두 개의 구간으로 나눠 각각 합병 정렬을 재귀적으로 수행하고, 두 구간을 하나로 합치며 정렬을 수행합니다.
반복자(Iterator) 간의 뺄셈(-) 연산은 반복자 사이의 거리(Distance)를 반환합니다.
즉, last - first은 구간 안의 원소의 갯수를 의미합니다.
std::inplace_merge는 정렬된 두 구간을 하나로 합치는 함수입니다.
퀵 정렬
출처: 위키백과
퀵 정렬(Quick Sort)은 원소 하나를 기준(Pivot)으로 잡고, 기준 보다 큰 원소와 작은 원소로 나누며 정렬을 수행하는 알고리즘입니다.
namespace sort {
template<std::random_access_iterator I,
std::sentinel_for<I> S,
typename Compare = std::less<>>
void quick_sort(I first, S last, Compare cmp = Compare{}) {
if (last - first > 1) {
auto pivot = *(first + (last - first) / 2);
auto middle1 = std::partition(first, last, [cmp, pivot](const auto &element) {
return cmp(element, pivot);
});
auto middle2 = std::partition(middle1, last, [cmp, pivot](const auto &element) {
return !cmp(pivot, element);
});
quick_sort(first, middle1, cmp);
quick_sort(middle2, last, cmp);
}
}
} // namespace sort
pivot은 합병 정렬의 middle에 *가 붙은 형태로, 반복자의 실질적인 값을 의미합니다.
std::partition은 조건에 참(True)인 원소가 거짓(False)인 원소 앞에 오도록 재배치하고 그 기준을 반환합니다.
재배치하는 과정에서 원소들이 자동으로 정렬되는 것이 아니기 때문에, 두 번의 partition이 필요합니다.
힙 정렬
출처: 위키백과
힙 정렬(Heap Sort)은 최대 힙 트리를 먼저 구성하고, 힙 트리에서 최댓값을 빼면서 자료를 정렬하는 알고리즘입니다.
namespace sort {
template<std::random_access_iterator I,
std::sentinel_for<I> S,
typename Compare = std::less<>>
void heap_sort(I first, S last, Compare cmp = Compare{}) {
std::make_heap(first, last, cmp);
while (first != last) {
std::pop_heap(first, last--, cmp);
}
}
} // namespace sort
std::make_heap를 이용하면 주어진 구간의 원소를 최대 힙 트리 배열 형태로 재배치 할 수 있습니다.
재배치된 구간에서 std::pop_heap를 이용해 최댓값을 구간의 맨 뒤로 보내는 것을 반복하는 구간의 원소가 정렬됩니다.
알고리즘 속도 비교
합병 정렬, 퀵 정렬, 힙 정렬이 전반적으로 빠른 속도를 보였고, 배열의 크기가 작을 때 삽입 정렬도 매우 빠르게 동작하는 것을 확인할 수 있었습니다.