쉘 정렬

10만개의 랜덤한 순서의 데이터를 정렬할 경우

쉘 정렬이 삽입정렬보다 300배 이상 빠른 걸 볼 수 있다

데이터의 개수라던가, 초기 데이터가 어떻게 나열되있냐에 따라 오차가 있겠지만, 어쨌든 속도차이가 압도적이라는 사실은 변함없다

 

게다가 구현하기도 막 힘든게 아니라서 사용도 편하다

데이터를 절반으로 잘라서 움짤처럼 묶어서 삽입정렬을 한다

그리고 그걸 다 합치고 다시 절반의 절반으로 다시 자르고 삽입정렬을 한다

이걸 하나씩 다 잘릴때까지 반복하면 정렬 끝

class ShellSorter
    {
        public static int[] SortData(int[] data)
        {
            int gap = data.Length / 2;
            int length = data.Length;

            while (gap != 0)
            {
                for (int i = 0; i < gap; i++)//자르고 새로 묶은 리스트끼리 정렬하기 위한 반복
                {
                    //삽입정렬 실행
                   data = SortInsert(data, i, gap);
                }
                gap /= 2; //자르는 간격 반으로 줄이기
            }

            return data;
        }

        static int[] SortInsert(int[] data, int start, int gap)
        {
            for (int i = start + gap; i < data.Length; i += gap) //같은 리스트끼리 gap만큼 떨어져있으니 i도 gap만큼 더해주면서 반복
            {
                for (int j = i - gap; j >= 0; j -= gap) //자기보다 앞에있는 애들과 비교하기 위한 반복
                {
                    if (data[j + gap] < data[j]) // 더 작으면 위치 바꾸고 아니면 멈춤
                    {
                        int temp = data[j + gap];
                        data[j + gap] = data[j];
                        data[j] = temp;
                    }
                    else break;
                }
            }

            return data;
        }
    }

예시 실행결과

 

빨라지는 원리는 삽입정렬의 단점을 보완한 건데,

원래 있던 위치가 정렬되야하는 위치가 멀리 떨어져 있으면 교환이 많이 일어나서 느려지게 된다

"멀리 떨어져있을 때 교환이 많이 일어난다" 의 문제를 해결하기 위해, 삽입정렬을 실행하는 그룹 자체를 쪼개서 정렬을 진행한다.

그럼 각 그룹 내에선 정렬이 이루어졌으니 그 다음 정렬땐 자신이 가야하는 위치와 더 가까워질 것이고 반복하면 또 가까워질 것이고...

이런식으로 하면 끝에가서는 결국 교환이 크게 일어나지 않고서 정렬을 완료할 수 있다