C#의 쉘 정렬 프로그램

셸 정렬을 사용하면 배열에서 멀리 떨어져 있는 항목을 교환한 다음 그 사이의 간격을 줄일 수 있습니다. 이것은 일종의 삽입 정렬의 일반화입니다. Shell Sort는 처음에 Donald Shell이 ​​출판한 것으로 알려져 있습니다.

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() 함수에서 먼저 초기 배열이 표시됩니다. 그런 다음, 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() 함수에서 주어진 배열은 while 루프와 for 루프를 사용하여 정렬됩니다. 쉘 정렬에 사용된 간격은 3입니다. 이에 대한 코드 스니펫은 다음과 같습니다.

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;
   }
}