쉘 정렬은 삽입 정렬을 개선한 알고리즘으로, Donald Shell이 1959년에 발표했습니다.

개요

쉘 정렬은 삽입 정렬을 단계적으로 적용하여 부분 리스트를 정렬하는 방식으로 동작합니다. 리스트의 요소들을 일정한 간격(인터벌)으로 묶어 부분 리스트를 만든 후, 각 부분 리스트를 삽입 정렬을 이용하여 정렬합니다. 이후에는 간격을 줄이면서 계속해서 부분 리스트를 정렬하고, 마지막에는 간격을 1로 설정하여 전체 리스트를 최종적으로 정렬합니다.

예시

다음은 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 = sizeof(arr) / sizeof(arr[0]);
    shellSort(arr, n);
    cout << "정렬된 배열: \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

시간 복잡도

쉘 정렬의 시간 복잡도는 입력 데이터의 상태에 따라 다르지만, 일반적으로 O(n log^2 n) 보다는 빠르고, 삽입 정렬보다 빠르며, 성능이 괜찮은 정렬 알고리즘이라고 할 수 있습니다.

결론

쉘 정렬은 삽입 정렬의 장단점을 보완한 알고리즘으로, 중간단계의 리스트가 정렬되어 있기 때문에 비교적 빠른 정렬 알고리즘 중 하나입니다. 어느 정도 크기의 리스트에서도 효율적으로 동작하므로, 정렬 알고리즘을 선택할 때 고려해볼 만 합니다.

더 많은 정보를 원하신다면 다음 참고문헌을 참조하시기 바랍니다.

• Donald Shell, “A High-Speed Sorting Procedure”, Communications of the ACM, vol. 2, no. 7, pp. 30-32, July 1959.