셸 정렬

셸 정렬

도날드 셸(D. L. Shell)에 의해 고안되었으며, 퀵 정렬이 나오기 전까지 가장 빠른 정렬 알고리즘이었다.

셸 정렬은 단순 삽입 정렬의 장점은 살리면서 단점은 보완하여 좀 더 빠르게 정렬 가능한 정렬 알고리즘이다.

일정한 간격으로 서로 떨어져 있는 두 요소를 그룹으로 묶어 대략 정렬을 수행하고, 간격을 좁혀 그룹의 수를 줄이면서 정렬을 반복하여 요소의 이동 횟루를 줄이는 정렬 알고리즘이다.

---

단순 삽입 정렬 장점 :

배열이 이미 많은 부분 정렬되어 있을 시 정렬 속도가 굉장히 빠르다.

 

단순 삽입 정렬 단점 :

삽입할 곳이 멀리 떨어져 있을 시 거리에 비례해서 이동하는 횟수가 많아진다.

-> 삽입할 위치와 현재 위치 사이에 위치한 요소들을 현재 위치까지 모두 한 칸씩 이동 시키고 삽입해야한다.

 

 

---

셸 정렬 방식

이해를 위해서 위의 그림과 같이 8개 요소를 갖는 배열이 있을때 배열의 크기/2를 하면 4가된다. 이렇게 4개씩 하나로 묶어 영역을 만들면 2개의 영역이 생기고 각 영역은 4개의 요소가 있으며 이때 각 영역의 각 요소의 위치가 같은 것끼리 묶으면 총 4개의 그룹이 생기게 된다. 그런 후 각 그룹을 정렬하면 이동이 있을 경우 이동 횟수가 1회씩 발생한다. 다음으로 다시 n/2를 하면 2가되고 위와 같이 2개씩 하나의 영역으로 묶으면 총 4개 영역이 생기며 각 영역은 2개의 요소를 갖고 있다. 이때 다시 영역의 같은 위치에 있는 요소들끼리 묶으면 4개 영역이기에 4개 요소가 하나의 그룹으로 총 2개의 그룹이 생긴다. 그럼 다시 그룹끼리 정렬을 하고 n/2를 했을 시 1이되므로 최종적으로 단순 삽입정렬을 수행한다.

---

Version1) 증분값(h/2)로 설정

   static void shellSort(int[] a , int n){
        for(int h = n / 2 ; h > 0 ; h/=2){ //비교할 대상 사이 거리
            for(int i = h ; i < n ; i++){
                int j;
                int tmp = a[i];
                for(j = i - h; j >= 0 && a[j] > tmp ; j -= h){
                    a[ j + h] = a[j];
                }
                a[j + h] = tmp;
            }
        }
    }

코드를 보면 처음 절반으로 나누어 비교대상 간 간격을 조정한다. 만약 16개의 요소가 있다고 한다면 각 요소 사이에는 8칸의 거리가 있게되는 것이다. 이처럼 비교를 통하여 대략 정렬을 수행하고 다음으로 반으로 줄여 4칸마다 있는 요소들을 한 그룹으로 하여 정렬을 수행한다. 이렇게 계속 줄여나가며 최종적으로는 단순 삽입 정렬과 동일하게 이웃하는 요소부터 1칸씩 이동하여 비교-정렬을 수행 후 모든 요소가 정렬된다.

 

여기서 생각해볼 것은 만약 단순 삽입정렬로 했을 경우 삽입하기 위해 선택한 요소와 삽입 위치 사이에 모든 수들은 비교와 이동을 해야한다. 그러나 셸 정렬로 정렬 시에는 증분값(h)에 따라 비교-교환이 이루어지기에 이동횟수를 줄일 수 있으며, 최종적으로 단순 삽입 정렬을 할 시 대략적으로 정렬을 마친 상태이기에 단순 삽입 정렬의 장점도 살릴 수 있습니다.

 

다음으로 배열의 크기에 따라서 증분값이 ......->8->4->2->1 이런식으로 나오는 경우가 있다.

이럴경우 각각의 증분값에 대해서 그룹이 형성될 때 전체적으로는 홀수,짝수 요수들만으로 그룹이 형성되면서 서로가 섞이지 않는 경우들이 발생한다. 셸 정렬은 단순 삽입 정렬의 다수이동발생이라는 단점을 보완하기 위해 고안 되었으나, 한정적인 그룹형성으로 효과가 떨어지는 상황이 생길 수 있다. 이를 보완하기 위해 아래와 같이 증분값을 최종적으로 1이 되는 시점부터 3 * h + 1을 하여 증분값을 구하고 증분값을 3씩 나누어가며 수행하면 효과를 올릴 수 있다.

---

Version2) 증분값(h/3 -1)로 설정

  static void shellSort(int[] a , int n){
        int h;
        for(h = 1; h < n ; h=h*3+1);

        for(;h > 0 ; h/=3){
            for(int i = h; i < n; i++){
                int j;
                int tmp = a[i];
                for(j = i - h; j >= 0 && a[j] > tmp ; j -= h)
                    a[j+h] = a[j];
                a[j+h] = tmp;
            }
        }
    }