[c++] 쉘정렬

12 Dec 2023

쉘 정렬의 가장 큰 특징은 간격을 조정해가면서 여러번의 삽입 정렬을 수행한다는 점입니다. 초기에는 큰 간격으로 요소를 비교하고 교환하는데, 이후 간격을 점차 줄여가며 정렬을 완성해나갑니다.

쉘 정렬의 시간 복잡도는 O(n log n)에 가까운 성능을 보이며, 특히 큰 규모의 배열을 정렬할 때 유용합니다.

다음은 C++로 구현된 쉘 정렬의 간단한 예시 코드입니다.

#include <iostream>
using namespace std;

void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i += 1) {
            int 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() {
    int arr[] = {12, 34, 54, 2, 3};
    int n = 5;
    shellSort(arr, n);
    cout << "정렬된 배열: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

위 코드에서 shellSort 함수는 쉘 정렬을 수행하고, main 함수에서는 쉘 정렬이 올바르게 작동하는지 확인하기 위해 간단한 배열을 정렬하고 출력합니다.

참고문헌:

https://en.wikipedia.org/wiki/Shellsort