쉘 정렬 (shell sort)

1. 쉘 정렬(Shell sort)

: 가장 오래된 정렬 알고리즘의 하나로, 삽입 정렬을 기본으로 삽입 정렬을 보완한 알고리즘이다. 

삽입 정렬은 요소들이 삽입될 때, 이웃한 위치로만 이동한다. 즉, 삽입되어야 할 위치가 현재 위치에서 멀리 떨어져있다면 여러번의 이동을 거쳐야만 제자리로 갈 수 있다. 이러한 점을 보완한 알고리즘이 쉘 정렬이다.

갭(gap)이 있는 쉘 정렬

• 정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분 리스트 생성, 이때 k를 간격(gap)이라고 한다.
• 간격의 초기값은 보통 2로 나눈 값으로 진행하는데, 3으로 나눈 후 1을 더하는 경우가 더 빠르다고 알려져있다.   즉, N/2 보다 (N/3) + 1이 더 빠르다는 얘기이다.
• 각 회전마다 간격 k를 절반으로 줄인다. 즉, 각 회전이 반복될 때마다 하나의 부분 리스트에 속한 값들의 개수를 증가한다.
• 간격 k가 1이 될 때까지 반복한다.

※ 쉘 정렬은 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동하게 된다. 즉, 교환 되는 요소들이 삽입 정렬보다는 최종 위치에 있을 가능성이 높고, 삽입 정렬보다 더 빠르게 수행 가능하다.

 

 

2. 예제

- 배열에 10, 3, 4, 20, 9, 16, 7, 13, 12이 저장되어 있다고 가정 -> 오름차순 정렬

 

1회전 : 

2회전 :

3회전 : 

 

결과 :

 

 

3. Java 쉘 정렬 예제

import java.util.Arrays;
 
public class shellSort {
    public static void intervalSort(int a[], int begin, int end, int interval) {
        int j;
        for(int i=begin+interval;i<=end;i=i+interval) {
            int item = a[i];
            for(j = i-interval;j>=begin && item<a[j]; j=j-interval) {
                a[j+interval] = a[j];
            }
            a[j+interval] = item;
        }
    }
    public static void shellSort(int[] a, int size) {
        System.out.println("정렬할 원소:"+Arrays.toString(a));
        System.out.println("-----------------셸 정렬 수행------------------");
        int interval = size/2;
        while (interval >=1){
            for(int i=0;i<interval;i++) {
                intervalSort(a, i, size-1, interval);
            }
            System.out.println("interval = "+interval);
            for(int t=0;t<size;t++) {
                System.out.print(a[t]+" ");
            }
            System.out.println();
            interval = interval/2;
        }
    }
    
    public static void main(String[] args) {
        int[] list = {10, 3, 4, 20, 9, 16, 7, 13, 12};
        int size = list.length;
        shellSort(list, size);
    }
 
}
 

 

4. 시간 복잡도

데이터의 개수를 n개라고 가정한다면,

평균 O(n^1.5)의 시간 복잡도부터 최악의 경우 O(n^2)의 시간 복잡도를 가지게 된다.