셸 정렬 알고리즘

단순 삽입 정렬의 장점(정렬을 마친 상태에 가까울 수록 정렬 속도가 매우 빨라짐)은 그대로 가져가고

단점(삽입할 위치가 멀리 떨어져 있으면 이동해야하는 횟수가 많아짐)을 보완한 알고리즘.

정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법.

 

자바로 구현하기

static void shellSort(int[] a, int n) {
    //각 부분 리스트의 요소가 1이 될 때까지,
    //즉 증분값 h가 1이 될 때까지 전체 반복
    for(int h=n/2; h>0; h/=2) {
        //부분 리스트들끼리 나눠서 반복할 수도 있지만 여기서는
        //전체 요소들을 반복하면서 각 부분 리스트에 맞게 비교 되도록 구현하겠다.
        for(int i=h; i<n; i++) {
            int tmp = a[i];
            int j;
            for(j=i-h; j>=0&&a[j]>tmp; j-=h) {
                a[j+h] = a[j];
            }
            a[j+h] = tmp;
        }
    }
}

 

gmlwjd9405.github.io/2018/05/08/algorithm-shell-sort.html

[알고리즘] 셸 정렬(shell sort)이란 - Heee's Development Blog