셸 정렬(Shell Sort)

• 셸 정렬

삽입 정렬의 장점을 활용하는 정렬 알고리즘

(삽입 정렬은 어느정도 정렬된 배열에서 최적의 성능을 냄)

데이더들을 일정 간격으로 그룹화 하고, 각 그룹에서 같은 자리의 데이터 끼리 삽입정렬(ex.각 그룹의 첫번째 자리 끼리)

그룹의 간격을 점점 줄여나감

최종적으론 어느정도 정렬된 상태에서 삽입 정렬을 하게됨

//셸 정렬(*Array : 정렬할 데이터 배열, Length : 배열 길이(데이터의 수), div : 그룹화 배수)

void Sort::ShellSort(int * Array, const int Length, const int div)

{

        int target, k;

        int begin;

 

        //간격 계산

        for (int interval = Length / 2; interval > 0; interval /= div)

        {

               //그룹에서 포지션 -> 그룹에서 첫번째, 두번째 ...

               for (int posInGroup = 0; posInGroup < interval; posInGroup++)

               {

                       begin = posInGroup;

 

                       //삽입정렬

                       for (int i = begin + interval; i < Length; i += interval)

                       {

                              target = Array[i];

 

                              for (k = i - interval; k >= begin && target < Array[k]; k -= interval)

                              {

                                      Array[k + interval] = Array[k];

                              }

 

                              Array[k + interval] = target;

 

                       }

               }

        }

}