셸 정렬(Shell Sort)

셸 정렬은 도널드 셸이 처음으로 제안했습니다. 셸 정렬은 빅데이터보다는 중간 규모(약 6000여개)의 데이터셋에 적합합니다.

주어진 입력 파일을 매개 변수의 값에 따라 여러 개의 부 파일로 나누고, 각 부 파일은 삽입 정렬 기법으로 정렬하는 과정을 되풀이하는 방법. 매개 변수의 값으로 먼저 적절한 값을 선택하고, 이를 점차 감소시켜 가면서 셸 정렬을 수행하면 매개 변수가 ‘1’이 될 때 종료된다.

셸 정렬(Shell Sort)은 바로 인접한 이웃 대신 고정된 거리 마큼 서로 떨어진 데이터 포인트끼리 묶어 이들을 정렬합니다. 첫 번째 패스는 바로 인접한 이웃들이 아닌 고정된 거리만큼 떨어진 두 데이터 포인트를 비교하여 정렬합니다. 두 번째 패스는 네 개의 데이터 포인트로 구성된 하위 리스트를 정렬합나다. 세 번째와 네 번째 패스를 보면 하위 리스트에 담긴 데이터 포인트의 개수가 점차 증가하며, 하위 리스트의 개수는 줄어드는 것을 볼 수 있습니다. 이 작업은 하나의 리스트에 모든 데이터 포인트가 들어갈 때까지 반복하다가 정렬 작업을 종료합니다.

 

C언어]

//정수형에 대한 셸정렬을 함수화하면 아래와 같다.

void ShellSort(int nr, int nx, int X[], int R[])

{

   //int nr : 정렬될 값들이 들어 있는 방수 변수

   //int nx : 매개변수 값들이 들어 있는 방수 변수

   //int X[] : 간격을 결정하는 매개 변수 값들이 있는 변수

   //int R[] : 정렬될 값들이 있는 배열 변수

   int a, b, c; //배열의 방을 결정할 변수

   int x;//매개 변수 값을 받을 변수

   int key;//비교할 값을 키 값으로 할 변수

 

   for(a=nx;a>0;a--)//x[]의 방의 개수 만큼 반복 작업을 선언한다.

   {

      x=X[a-1];//매개 변수 배열의 마지막 방의 값을 x에 치환한다.

 

      //매개 변수 값부터 nr-1까지의 방값을 키 값으로 하는 반복 작업을 선언한다.

      for(b=x;b<nr;b++)

      {

         key=R[b];

         c=b-x;

         while(c>=0 && R[c]>key)

         {

            R[c+x]=R[c]; //x만큼 떨어진 방의 값과 교환한다.

            R[c]=key;

            c=c-x;

         }

      }

   }

}

 

 

Python]

def ShellSort(list):

    distance = len(list) // 2;

    while distance > 0:

        for i in range(distance, len(list)):

            temp = list[i]

            j=1

            #하위 리스트 안에 든 요소들을 정렬한다.

            while j >= distance and list[j-destance] > temp:

                list[j] = list[j-distance]

                j = j - distance

            list[j] = temp

        #다음 패스를 위해 거리를 반으로 줄인다.

        distance //= 2

 

    return list

 

출처]

한국정보통신기술협회 : 셸 정렬
프로그래머가 알아야 할 알고리즘 40(길벗) : 셸 정렬(p086)

 

참고 문제]

 

 

 

※ 10월 25일은 독도의 날입니다.

대한민국의 아름다운 영토, 독도의 봄