자바로 구현한 셀 정렬(Shell Sort) 알고리즘

셀 정렬은 삽입 정렬을 기반으로 단점은 최소화하고 장점은 최대화 한 정렬 방식입니다.

만약에 삽입 정렬에 대해 모르신다면 삽입 정렬글을 읽고 오시는 것을 추천드립니다.

https://kkungchan.tistory.com/287

자바로 구현한 삽입 정렬 알고리즘

 

삽입 정렬의 단점은 역순으로 정렬되어 있다면 교환이 너무 많이 생겨 시간이 최악의 경우 O(N²)의 시간 복잡도를 가진다는 것입니다. 

반대로 삽입 정렬의 장점은 정렬이 어느 정도 되어 있다면 O(N)으로 최고로 좋은 시간 복잡도의 성능을 보여주는 장단점이 있었습니다.

그렇다면 셀 정렬은 무엇일까요? 삽입정렬의 장점을 최대화할 수 있도록 미리 어느 정도 정렬을 해준 다음에 삽입 정렬을 진행하는 방식의 정렬 알고리즘을 의미합니다.

미리 어느 정도 정렬을 해준다면 최고의 성능 O(N)까지는 갈 수 없겠지만 최악 O(N²)의 시간 복잡도는 막을 수 있을 것입니다. 그렇다면 어떻게 미리 정렬을 하는지 특징을 살펴본 후에 설명하도록 하겠습니다.

 

셀 정렬의 특징으로는 1. 비교 정렬입니다. 2. 제자리 정렬입니다. 3. 안정 정렬이 아닙니다.

 

1. 비교 정렬 : 서로 값을 비교하여 정렬하는 알고리즘입니다.

2. 제자리 정렬 : 해당 배열 외에 또 다른 배열의 저장 공간이 필요가 없습니다.

3. 안정정렬 : 같은 값일 경우 해당 정렬이 변경되지 않습니다.

 

셀 정렬 과정을 요약하면 다음과 같습니다.

1. 갭을 설정합니다.

2. 갭만을 기준으로 간격을 주면서 삽입정렬을 실행합니다.

3. 갭이 1이 될 때까지 삽입 정렬 반복합니다.

 

셀 정렬은 어떻게 미리 정렬을 어느 정도 해놓을 것인가를 고민하는 것이 중요합니다.

그래서 얻은 답이 삽입 정렬처럼 근접해 있는 원소끼리를 교환하는 것이 아니라 어느 정도 gap이 있는 원소끼리 비교해 교환해 나가는 것입니다. 그리고 그 gap을 줄여서 비교하다 보면 정렬 기준에 가까워질 것이라는 생각으로 만든 알고리즘이 셀 정렬입니다. 

그림으로 설명하겠습니다.

---

---

 

 

해당 그림을 보면 굉장히 복잡해 보입니다. 

하지만 차근차근 보면 어렵지 않으니 하나하나 설명해 드리도록 하겠습니다.

먼저 round 1에서는 gap이 4로 설정한 후에 첫 target을 2로 정합니다. 그 후에 삽입 정렬이라면 그 타깃을 올바른 곳에 정렬하기 위해 또 비교해야 하지만 이미 2는 0번째 인덱스로 들어가 그 밑에 인덱스가 없어 비교할 수 없기 때문에 첫 정렬을 끝냅니다. 그다음 타깃을 정해 삽입 정렬을 진행합니다. 그렇게 삽입정렬을 할 수 있을 만큼 삽입 정렬을 하고 round을 끝냅니다.

round 2에서 target 4와 6을 보면 target이 된 인덱스에서 아래 인덱스에서 좀 더 비교할 수 있기 때문에 좀 더 비교를 해주는 것을 확인할 수 있습니다.

그렇게 gap을 기준으로 삽입 정렬 해주고 1이 되었을 때 정렬을 종료합니다.

그냥 삽입정렬하는게 좀 더 빠르지 않을까요?

그럴 수 도 있습니다. 하지만 셀 정렬의 목적은 최고 속도를 출력하는 것이 아닌 최악의 속도를 막는 것이고 실제로 교환할때 시간을 많이 쓰는데 round 2의 target 2일 때를 보면 한 번에 올바른 인덱스를 찾아갔기 때문에 더 이상 교환이 이루 지지 않았습니다. 

 

그러면 gap을 어떻게 정할까요? 그림에서는 편의를 위해서 4 -> 2 -> 1로 줄어든다고 명시했지만 사실 성능 별로 계산한 gap을 정하는 방법이 있습니다. 아래 표를 보겠습니다.

여기서 저는 A102549(Ciura Sequence) gap을 사용하도록 하겠습니다. 

참조 블로그에서 이 gap이 가장 좋은 성능을 보였다고 하네요.

 

그럼 자바로 구현을 해보도록 하겠습니다.

전체 코드

public class Shell_sort {

    private final static int[] CIURA_SEQUENCE =
            { 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) {
        int[] array = new int[100];

        //배열에 난수 저장
        for(int i=0; i<array.length; i++){
            array[i] = (int)(Math.random()*100);
        }

        //정렬전 배열
        for(int i=0; i<array.length; i++){
            System.out.printf("%d ",array[i]);
            if((i+1)%10 == 0){
                System.out.println();
            }
        }

        //선택 정렬
        shell_sort(array);

        System.out.println();
        System.out.println();

        //정렬후 배열
        for(int i=0; i<array.length; i++){
            System.out.printf("%d ",array[i]);
            if((i+1)%10 == 0){
                System.out.println();
            }
        }
    }

    //gap을 구하는 함수
    private static int getGap(int size){
        int gap_index = 0;
        //size보다 작을때까지 반복하면서 원하는 인덱스를 찾는다.
        while(CIURA_SEQUENCE[gap_index] < size) gap_index++;
        return gap_index-1;//마지막에 인덱스가 1커지고 반복이 종료됨으로 -1을 해준다.
    }
    
    //셀 정렬 함수
    public static void shell_sort(int[] array){

        int gapIndex = getGap(array.length);//gap을 가져온다.

        //gap이 1이 될때까지 반복한다.
        for(int i = gapIndex; i >=0; i--){
            insert_sort(array,CIURA_SEQUENCE[i]);
        }
    }
    
    //셀 정렬 안에 삽입정렬
    private static void insert_sort(int[] array,int gap){
        //삽입정렬을 하기 위해 리스트의 인덱스를 차례로 늘린다.
        for(int i=0; i<array.length; i++){
            if(i+gap > array.length-1) break; //i+gap이 넘어가는 에러 방지
            int target = array[i+gap];//target 설정
            int j=i;//target과 비교할 인덱스 설정

            /*
            * 비교 당하는 원소의 인덱스가 0보다 작아지거나
            * 원소의 위치가 gap을 기준으로 올바른 위치라고 판단되면
            * 반복을 종료한다.
            */
            while(j>=0 && target < array[j]){
                array[j + gap] = array[j];//해당 원소를 뒤로 민다.
                j -= gap;//비교할 원소의 인덱스를 gap을 기준으로 낮춘다.
            }

            //반복이 끝났다면 해당 위치에 target값을 넣어준다.
            array[j+gap] = target;
        }
    }

}

중요한 함수는 shell_sort와 insert_sort 입니다.

//셀 정렬 함수
public static void shell_sort(int[] array){

    int gapIndex = getGap(array.length);//gap을 가져온다.

    //gap이 1이 될때까지 반복한다.
    for(int i = gapIndex; i >=0; i--){
        insert_sort(array,CIURA_SEQUENCE[i]);
    }
}

//셀 정렬 안에 삽입정렬
private static void insert_sort(int[] array,int gap){
    //삽입정렬을 하기 위해 리스트의 인덱스를 차례로 늘린다.
    for(int i=0; i<array.length; i++){
        if(i+gap > array.length-1) break; //i+gap이 넘어가는 에러 방지
        int target = array[i+gap];//target 설정
        int j=i;//target과 비교할 인덱스 설정

        /*
        * 비교 당하는 원소의 인덱스가 0보다 작아지거나
        * 원소의 위치가 gap을 기준으로 올바른 위치라고 판단되면
        * 반복을 종료한다.
        */
        while(j>=0 && target < array[j]){
            array[j + gap] = array[j];//해당 원소를 뒤로 민다.
            j -= gap;//비교할 원소의 인덱스를 gap을 기준으로 낮춘다.
        }

        //반복이 끝났다면 해당 위치에 target값을 넣어준다.
        array[j+gap] = target;
    }
}

gap을 기준으로 삽입 정렬 할 수 있도록 gap을 삽입정렬 함수에 넘겨주고 삽입정렬을 gap을 기준으로 진행해 줍니다. 코드는 삽입정렬과 매우 흡사하니 삽입정렬을 안다면 해당 코드를 어렵지 않게 이해하실 수 있을 겁니다.

 

위에 해당 코드를 이해했다면 좀 더 짦은 형식의 코드로 변경할 수 있습니다.

//셀 정렬 함수
public static void shell_sort(int[] array) {

    int gapIndex = getGap(array.length);//gap을 가져온다.

    //gap이 1이 될때까지 반복
    while (gapIndex >= 0) {
        int gap = CIURA_SEQUENCE[gapIndex--];
        //비교하는 target은 원소 하나씩 증가함
        for(int i = gap; i<array.length; i++){
            /*
            target원소가 gap을 기준으로 올바른 위치에 지정되거나
            target의 이동 후 인덱스가 gap보다 작은 경우 반복을 종료
            */
            for(int j=i; j>=gap && array[j] < array[j-gap]; j-=gap){
                swap(array,j,j-gap);
            }
        }

    }
}

private static void swap(int[] array, int i, int min){
    int temp = array[i];
    array[i] = array[min];
    array[min] = temp;
}

해당 코드는 swap을 통해 원소를 뒤로 미루고 target을 다시 입력하는 과정을 생략하고 셀 정렬을 하도록 만든 코드입니다. 주석을 통해 자세히 설명하였지만 먼저 gap이 1이 될 때까지 while문을 돌리고 gap을 기준으로 target을 정하고 그 target이 올바른 위치를 찾거나 target이 이동 후에 인덱스가 gap보다 작으면(target과 비교할 인덱스가 음수가 되어서 에러가 됨으로) 반복을 종료하는 코드입니다.

 

 

 

 

장점

1. 멀리 있는 원소들끼리 빠르게 비교 및 교환이 이루어진다.

2. 삽입 정렬, 거품 정렬에 비해 속도가 빠르다.

 

단점

1. 일반적인 삽입정렬에 비해 구현이 까다롭다.

2. gap sequence에 영향을 많이 받으며 적절한 gap설정이 필요하다.

3. 일정 간격을 두고 원소 교환이 이루어지기 때문에 안정정렬이 아니다.

 

 

다음 블로그를 참고하였습니다.

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

자바 [JAVA] - 셸 정렬 (Shell Sort)