Study/Algorithm

정렬 알고리즘(3) - (쉘 정렬)

MWP 2017. 3. 12. 19:16



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    public static void sort(int[] arr){
        int N = arr.length;
        int h = 1; // h 개 만큼 점프하면서 비교
        
        while(h<N/3)h = h*3 +1; // 최적의 h 값을 구하는 공식
        
        while(h >=1){
            for(int i=h; i< N ; i++){
                for(int j = i; j>=h && arr[j]<arr[j-h];j-=h){
                    // j를 인덱스로 h 만큼 접프하면서(j-=h) 비교한다. 
                        //인덱스 j 가 h보다 작으면 앞에 비교할 대상이 없다는 의미
                    int t = arr[j];
                    arr[j] = arr[j-h];
                    arr[j-h] = t;
                }
            }
            h/=3; // h 를 3으로 나누어준다 결국 h==1 이 될때 삽입정렬이 이루어짐
        }
    }



h 개 떨어진 원소들 간에 삽입정렬

의 수열을 사용한다


시간복잡도 :  


공간복잡도 :  


* 삽입정렬을 개선한 알고리즘 (삽입정렬보다 데이터 이동이 적다)

* 최선의 수열은 아직 발견되고 있지 않음

* 수열이 길면 단계 수 증가, 수열이 짧으면 성능 향상 정도가 미약 ( 성능이 h에 비례 )