셸 정렬(Shell Sort)에 대해 알아보자!

셸 정렬

• 오름차순을 기준으로 정렬.
• 삽입정렬을 보완한 알고리즘.
• 배열을 일정한 기준의 간격으로 분류(부분 리스트를 생성).
• 부분 리스트에서 삽입정렬을 수행.
• 이 과정을 간격이 1일때까지 반복 수행.

<이미지 출처: https://gmlwjd9405.github.io/images/algorithm-shell-sort/shell-sort.png>

---

셸 정렬 C# 코드

public void Shell_Sort(int[] array)
    {
        //1.매개변수 배열의 크기의 절반만큼 갭을 만든다.
        int gap;

        for (int i = array.Length / 2; i > 0; i = i / 2)
        {
            gap = i;

            //갭이 짝수면 갭+1. ex)배열크기=11. 갭=5,3,1
            if (gap % 2 == 0)
            {
                gap++;
            }

            for (int k = 0; k < gap; k++)
            {
                Shell_Insert_Sort(array, k, gap);
            }
        }

    }
    public void Shell_Insert_Sort(int[] array, int first, int gap)
    {
        int temp;

        for (int i = first + gap; i < array.Length; i += gap)
        {
            temp = array[i];

            for (int k = i - gap; k >= first && array[k] > temp; k -= gap)
            {
                temp = array[k + gap];
                array[k + gap] = array[k];
                array[k] = temp;
            }
        }
    }

 

• 장점
  - 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 비교적 더 큰 거리를 이동.
  - 부분 리스트에서 어느 정도 정렬을 해놓은 상태이기 때문에 기존 단순 삽입 정렬보다 더욱 빠른 수행능력.
  - 알고리즘이 간단하여 쉽게 구현 가능.

<이미지 출처: https://gmlwjd9405.github.io/images/algorithm-shell-sort/sort-time-complexity.png>

---