쉘 정렬(Shell Sort) 알고리즘 완벽 가이드: 개념부터 C++ 구현까지

쉘 정렬(Shell Sort)은 삽입 정렬(Insertion Sort)을 기반으로 한 정렬 기법입니다. 일반적인 삽입 정렬에서는 요소를 올바른 위치에 삽입하기 위해 대량의 데이터를 한꺼번에 이동(shift)해야 하는 비효율이 발생할 수 있습니다. 쉘 정렬은 이러한 문제를 해결하기 위해 고안되었으며, 특정 간격(gap)을 두고 떨어져 있는 요소들을 먼저 비교·교환함으로써 불필요한 이동 횟수를 크게 줄입니다.

쉘 정렬의 핵심 아이디어는 다음과 같습니다. 처음에는 배열 길이의 절반에 해당하는 넓은 간격으로 정렬을 시작하고, 매 패스(pass)가 끝날 때마다 간격을 절반씩 줄여 나갑니다. 마지막에는 간격이 1이 되어 사실상 일반적인 삽입 정렬과 동일하게 동작하지만, 이 시점에는 배열이 이미 거의 정렬된 상태이므로 전체 수행 속도가 크게 향상됩니다.

쉘 정렬의 시간 및 공간 복잡도

시간 복잡도: 최선의 경우 O(n log n), 그 외의 경우에는 사용하는 간격(gap) 수열에 따라 달라집니다.
공간 복잡도: O(1) — 제자리(in-place) 정렬 방식으로 추가 메모리가 거의 필요하지 않습니다.

입력 및 출력 예시

입력:
정렬되지 않은 리스트: 23 56 97 21 35 689 854 12 47 66

출력:
정렬 전 배열: 23 56 97 21 35 689 854 12 47 66
정렬 후 배열: 12 21 23 35 47 56 66 97 689 854

알고리즘

shellSort(array, size)

입력 − 데이터 배열과 배열 내 전체 요소 개수

출력 − 정렬이 완료된 배열

Begin
   for gap := size / 2, gap > 0 인 동안 gap := gap / 2 로 갱신하며 반복 do
      for j := gap 부터 size – 1 까지 do
         for k := j-gap 부터 0 이상인 동안 gap 값만큼 감소시키며 do
            if array[k+gap] >= array[k]
               break
            else
               array[k + gap] 과 array[k] 를 교환(swap)
         done
      done
   done
End

C++ 구현 예제

아래는 위 알고리즘을 C++로 구현한 전체 코드입니다. 사용자로부터 배열의 크기와 요소를 입력받아 쉘 정렬을 수행하고, 정렬 전후의 배열 상태를 출력합니다.

#include<iostream>
using namespace std;

void swapping(int &a, int &b) { // a와 b의 값을 서로 교환
   int temp;
   temp = a;
   a = b;
   b = temp;
}

void display(int *array, int size) { // 배열 출력 함수
   for(int i = 0; i<size; i++)
      cout << array[i] << " ";
   cout << endl;
}

void shellSort(int *arr, int n) { // 쉘 정렬 함수
   int gap, j, k;
   for(gap = n/2; gap > 0; gap = gap / 2) {     // 초기 gap = n/2, 이후 gap/2씩 감소
      for(j = gap; j<n; j++) {
         for(k = j-gap; k>=0; k -= gap) {
            if(arr[k+gap] >= arr[k])
               break;
            else
               swapping(arr[k+gap], arr[k]);
         }
      }
   }
}

int main() {
   int n;
   cout << "Enter the number of elements: ";
   cin >> n;
   int arr[n]; // 입력받은 크기만큼 배열 생성
   cout << "Enter elements:" << endl;

   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }

   cout << "Array before Sorting: ";
   display(arr, n);
   shellSort(arr, n);
   cout << "Array after Sorting: ";
   display(arr, n);
}

실행 결과

Enter the number of elements: 10
Enter elements:
23 56 97 21 35 689 854 12 47 66
Array before Sorting: 23 56 97 21 35 689 854 12 47 66
Array after Sorting: 12 21 23 35 47 56 66 97 689 854

정리

쉘 정렬은 삽입 정렬의 단점인 잦은 요소 이동을 간격(gap) 기반의 그룹별 정렬로 보완한 알고리즘입니다. 구현이 비교적 간단하면서도 추가 메모리를 거의 사용하지 않기 때문에, 중소 규모 데이터를 정렬할 때 실용적인 선택지가 됩니다. 다만 성능이 간격 수열 선택에 따라 달라질 수 있다는 점은 유의해야 합니다.