[Algorithm] 셸 정렬(Shell sort)

 

셸 정렬 기본 개념

"Donal L. Shell"이라는 사람이 제안한 방법으로, 삽입 정렬을 보안한 알고리즘이다. 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 빠르다는 것을 착안하였다. 삽입 정렬과 다르게 셸 정렬은 전체의 리스트를 한 번에 정렬하지 않는다.

 

셸 정렬 구체적인 개념

정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분 리스트를 만든다. 이때 k를 "간격(gap)"이라고 한다. 각 회전마다 간격 k를 절반으로 줄인다. 즉, 각 회전이 반복될 때마다 하나의 부분 리스트에 속한 값들의 개수는 증가한다.

간격의 초기값 : 정렬할 리스트 사이즈 / 2
분할된 리스트의 개수는 gap과 같다.
간격은 홀수로 하는 것이 좋다.
간격을 절반으로 줄일 때 짝수가 나오면 +1을 해서 홀수를 만든다.
간격 k가 1이 될 때까지 반복한다.

 

셸 정렬 알고리즘 예제

import java.util.Arrays;

public class ShellSort {

    public static void main(String[] args) {
        
        int[] unsortedArray = {11, 9, 7, 21, 5, 4, 23, 2, 1, 16};
        System.out.println("Array Before sorting: " + Arrays.toString(unsortedArray));
        System.out.println("Array After sorting : " + Arrays.toString(shellSort(unsortedArray)));
    }
    
    private static int[] shellSort(int[] arr) {
        
        int arrLength = arr.length;
        
        //gap 값을 반으로 줄이기 위한 for문
        for (int gap=arrLength/2; gap>0; gap/=2) {
            
            //gap이 짝수일 경우 홀수만들기
            if (gap%2 == 0) {
                gap++;
            }
            
            //gap 설정를 통한 부분 리스트
            for (int i=gap; i<arrLength; i++) {
                int element = arr[i], j = i;
                //부분 리스트 삽입 정렬
                while (j>=gap && arr[j-gap]>element) {
                    arr[j] = arr[j-gap];
                    j -= gap;
                }
                arr[j] = element;
                
            }
            System.out.println("gap " + gap + " swapped       : " + Arrays.toString(arr));
        }
        
        return arr;
    }
}

 

셸 정렬 알고리즘 특징

장점
연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 따라서 삽입 정렬보다는 최종 위치에 있을 가능성이 높아진다. 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 삽입 정렬보다 더욱 빠르게 수행된다. 알고리즘이 간단하여 프로그램으로 쉽게 구현 가능하다.

단순하지만 비효율적인 방법
- 버블 정렬, 선택 정렬, 삽입 정렬

복잡하지만 효율적인 방법
- 셸 정렬, 힙 정렬, 퀵 정렬, 병합 정렬

 

정렬 알고리즘 Post

[프로그래밍/Algorithm] - [Algorithm] 버블 정렬(Bubble sort)

[프로그래밍/Algorithm] - [Algorithm] 삽입 정렬(Insertion sort)

[프로그래밍/Algorithm] - [Algorithm] 선택 정렬(Selection sort)

[프로그래밍/Algorithm] - [Algorithm] 셸 정렬(Shell sort)