C#로 배우는 쉘 정렬(Shell Sort): 개념부터 코드 구현까지

쉘 정렬이란?

쉘 정렬(Shell Sort)은 배열에서 서로 멀리 떨어져 있는 요소들을 먼저 교환한 뒤, 점차 요소들 사이의 간격(gap)을 줄여가며 정렬을 수행하는 알고리즘입니다. 이는 삽입 정렬(Insertion Sort)을 일반화한 형태로 볼 수 있습니다.

삽입 정렬은 인접한 요소끼리만 비교하기 때문에 값이 멀리 이동해야 할 경우 비효율적이지만, 쉘 정렬은 넓은 간격에서부터 정렬을 시작해 데이터가 대략적으로 제자리에 가까워진 상태를 만든 후 마지막에 간격 1로 삽입 정렬을 수행하므로 전체적인 성능이 향상됩니다.

쉘 정렬이라는 이름은 이 알고리즘을 최초로 발표한 도널드 셸(Donald Shell)의 이름에서 유래했습니다.

C# 쉘 정렬 예제 코드

다음은 C#으로 쉘 정렬을 구현한 프로그램입니다.

using System;
namespace ShellSortDemo {
   public class Example {
      static void shellSort(int[] arr, int n) {
         int i, j, pos, temp;
         pos = 3;
         while (pos > 0) {
            for (i = 0; i < n; i++) {
               j = i;
               temp = arr[i];
               while ((j >= pos) && (arr[j - pos] > temp)) {
                  arr[j] = arr[j - pos];
                  j = j - pos;
               }
               arr[j] = temp;
            }
            if (pos / 2 != 0)
            pos = pos / 2;
            else if (pos == 1)
            pos = 0;
            else
            pos = 1;
         }
      }
      static void Main(string[] args) {
         int[] arr = new int[] { 56, 12, 99, 32, 1, 95, 25, 5, 100, 84 };
         int n = arr.Length;
         int i;
         Console.WriteLine("Shell Sort");
         Console.Write("Initial array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
         shellSort(arr, n);
         Console.Write("\nSorted Array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
      }
   }
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

Shell Sort
Initial array is: 56 12 99 32 1 95 25 5 100 84
Sorted Array is: 1 5 12 25 32 56 84 95 99 100

코드 상세 설명

Main() 함수

Main() 함수에서는 먼저 초기 배열을 선언하고 화면에 출력합니다. 그다음 shellSort() 함수를 호출하여 배열에 대해 쉘 정렬을 수행합니다. 해당 코드는 다음과 같습니다.

int[] arr = new int[] { 56, 12, 99, 32, 1, 95, 25, 5, 100, 84 };
int n = arr.Length;
int i;
Console.WriteLine("Shell Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
   Console.Write(arr[i] + " ");
}
shellSort(arr, n);

shellSort() 함수

shellSort() 함수 내부에서는 while 루프와 for 루프를 사용해 주어진 배열을 정렬합니다. 이 예제에서 사용되는 간격(gap)의 초기값은 3입니다. 각 패스가 끝날 때마다 간격을 절반으로 줄여가며, 간격이 1이 될 때까지 정렬을 반복합니다. 해당 코드는 다음과 같습니다.

static void shellSort(int[] arr, int n) {
   int i, j, pos, temp;
   pos = 3;
   while (pos > 0) {
      for (i = 0; i < n; i++) {
         j = i;
         temp = arr[i];
         while ((j >= pos) && (arr[j - pos] > temp)) {
            arr[j] = arr[j - pos];
            j = j - pos;
         }  
         arr[j] = temp;
      }
      if (pos / 2 != 0)
      pos = pos / 2;
      else if (pos == 1)
      pos = 0;
      else
      pos = 1;
   }
}

내부의 while 루프는 현재 위치에서 간격만큼 앞선 요소와 값을 비교하여, 더 큰 경우 해당 요소를 뒤로 밀어내는 삽입 정렬 방식으로 동작합니다. 이 과정을 통해 간격이 큰 상태에서는 요소들이 빠르게 대략적인 위치로 이동하게 되고, 간격이 1인 최종 단계에서는 거의 정렬된 배열에 대해 삽입 정렬이 수행되므로 효율성이 높아집니다.