정렬(sort) - 쉘 정렬(shell sort)

정렬(sort) - 쉘 정렬(shell sort)

쉘 정렬(shell sort)은 배열을 적당한 크기의 작은 그룹으로 나눠 그룹별 요소에 대하여 삽입 정렬 방법을 사용한다.

처음에는 나눌 수를 정하고 그 수만큼의 요소를 삽입 정렬 방법으로 정렬한다. 다시 좀 더 작은 수를 정하고 같은 방법으로 계속 반복 진행한다.

while(h >= 1){

  for(i=h; i<n ; i++){

    temp = a[j];

    for(j=i-h; j>= 0; j-=h){

      // 내림차순이면 부등호를 <로 변경

      if(a[j] > temp )

        a[j+h]=a[j];

      else

        break;

    }

    a[j+h] = temp;

  }

  // 비교의 간격은 3의 배수가 가장 효율적

  h/=3 ; 

}