[c++] 셸정렬
셸 정렬은 부분 리스트를 사용하여 정렬하는 알고리즘이다. 이 알고리즘의 아이디어는 서로 먼 요소들끼리 비교를 하여 서로 교환해 멀리 떨어져 있는 요소의 정렬을 먼저 수행하는 것이다.
셸 정렬의 일반적인 알고리즘은 다음과 같다.
#include <vector>
#include <iostream>
using namespace std;
template <typename T>
void shellSort(vector<T>& arr) {
int n = arr.size();
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
T temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
int main() {
vector<int> arr = {12, 34, 54, 2, 3};
shellSort(arr);
for (int x : arr) {
cout << x << " ";
}
return 0;
}
위의 코드는 벡터를 사용하여 정수를 정렬하는 셸 정렬의 예시이다.
셸 정렬은 평균 시간 복잡도가 O(n log^2 n)으로 빠른 편에 속하지만, 현재는 퀵 정렬(Quick Sort)이나 병합 정렬(Merge Sort)과 같은 새로운 알고리즘들이 개발되면서 자주 쓰이지는 않는다. 하지만 아직도 어떤 특정한 상황에서는 효과적으로 사용될 수 있다.
셸 정렬에 대한 더 자세한 정보는 다음 레퍼런스에서 확인할 수 있다.
- Sedgewick, R., & Wayne, K. (2011). 알고리즘(원정우, Trans.). 인사이트.
- https://en.wikipedia.org/wiki/Shellsort