Shell sort

개념

셀 정렬은 삽입정렬의 단점을 극복하고자 나온 알고리즘이다.

삽입정렬 알고리즘의 기존 비교간격(1) 이였지만, 쉘 정렬은 비교간격을 배열의 크기를 통해 구하고 점차 줄여서 정렬해 나가면서 비교간격(1) 까지 정렬하게 되면, 우리가 기존의 알고 있는 삽입정렬과 같아진다.
언뜻 보기에는 삽입정렬보다 더 많이 정렬 알고리즘을 수행하는 것처럼 보이지만, 실제로 그렇지 않다.

*cf) 삽입정렬 자신 이전의 원소들과 비교하여 정렬 알고리즘에 맞춰서 정렬하는 방식이다. 정렬 알고리즘에 역순으로 정렬되어 있는 배열일 수록 정렬하는데 많은 시간이 소요된다.

알고리즘 구현

1. 간격(gap)을 설정한다.

2. 각 간격별로 분류 된 서브(부분) 리스트에 대해 삽입정렬을 한다.

3. 각 서브(부분) 리스트의 정렬이 끝나면 간격을 줄인다.

4. 간격이 1이 될 때 까지 2번 과정으로 되돌아가며 반복한다.

*cf) 1번에 존재하는 간격을 어떻게 설정할까? 이것을 우리는 Gap Sequence 라고 하는데,
https://en.wikipedia.org/wiki/Shellsort#Gap_sequences 해당 링크에 여러 gap Sequence가 공식이 존재한다.
(솔직히 잘 모르겠다. 어떤식으로 gap sequence들이 유도되는지는...)

현재 알려진 gap Sequence들 중 가장 좋은 퍼포먼스를 보여주는 ciura 라는 시퀀스가 있다.

gap Sequence = {1, 4, 10, 23, 57, 132, 301, 701, 1750}
1750 이후로는 Gn=(Gn-1) *2.25 로 표현된다.

알고리즘 코드

public class Shell_sort {

    //경험에 의해 좋은 shell sort performance를 보여준 gap Sequence
    private final static int[] gap = { 1, 4, 10, 23, 57, 132, 301, 701, 1750, 3937,
            8858, 19930, 44842, 100894, 227011, 510774,
            1149241, 2585792, 5818032, 13090572, 29453787,
            66271020, 149109795, 335497038, 754868335, 1698453753};

    public static void main(String[] args) throws IOException {

        int [] arr = {9,7,1,2,3,5,6};

        //shell Sort gap Sequence 구하는 과정
        int index=0;
        //최소한 부분 배열의 원소가 2개씩은 비교 되도록 나눠준다. ..?
        int len = (int)(arr.length/2.25);
        while(gap[index]<len){
            index++;
        }

        System.out.println("index : " +index );
        // gap Sequence 를 통해 삽입 정렬 반복한다.

        //gap Sequence gap[index] 부터 gap[0] 까지 반복
        for(int i=index;i>=0;i--){


            //기본 삽입정렬  알고리즘
            for(int j=gap[i];j<arr.length;j+=gap[i]){
                int target = arr[j];
                int k= j-gap[i];

                //비교대상: 자기보다 먼저 나온 원소들
               while( k>=0 && target<arr[k] ){
                   arr[k+gap[i]]=arr[k];
                   k-=gap[i];
               }
               arr[k+gap[i]]=target;
            }
        }

        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }
}

Reference

https://st-lab.tistory.com/209