[자료구조] 셸 정렬(Shell Sort) with JAVA

[자료구조] 셸 정렬(Shell Sort) with JAVA

 

 

* 셸 정렬(Shell Sort)이란?

 일정한 간격으로 떨어져있는 자료들끼리 집합을 만들어 각각의 집합 내에서 삽입정렬(Insert Sort)을 수행하는 작업을 반복한다. 이 때, 일정한 간격을 세우는 기준 h는 원소 전체의 갯수/2 를 시작으로 하여 한 단계가 수행될 때마다 그 값을 반으로 감소시킨다. 이를 반복 수행하다보면 결국 h가 1이 될 때까지 반복하며 정렬을 마치게 된다. 전체 원소에 대하여 삽입 정렬을 수행하는 것보다 부분집합으로 정렬을 하면 비교 연산과 교환 연산의 횟수를 줄일 수 있다.

 

 

* 예제

 정렬되지 않은 수 {69,7,30,3,16,9,31,23} 를 셸 정렬을 이용하여 정렬하도록 하자.

 

1) 우선 매개변수 h는 8/2를 하여 h=4이다. 간격이 4만큼 떨어져 있는 원소들을 부분집합으로 만들어 비교한다. 

   * 부분집합 = {69, 16}, {7, 9}, {30, 31}, {3, 23}

   --> 이 부분집합 각각에 대하여 삽입정렬을 수행한다. 

 

   h=4로 셸 정렬 수행 후 = {16, 7, 30, 3, 69, 9, 31, 23}

 

 

2) h = 4/2 = 2 로 변경하여 다시 셸 정렬을 수행한다.

   * 부분집합 = {16, 30, 69, 31}, {7, 3, 9, 23}

   --> 이 부분집합 각각에 대하여 삽입정렬을 수행한다.

 

   h=2 로 셸 정렬을 수행한 후 = {16,30,31,69}, {3,7,9,23} = {16,3,30,7,31,9,69,23}

 

3) h = 2/2 = 1 로 변경하여 다시 셸 정렬을 수행한다.

  

   h=1 로 셸 정렬을 수행한 후 = {3,7,9,16,23,30,31,69}

 

 

* 셸 정렬 java코드

package Sort;
 
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 = {16, 7, 30, 3, 69, 9, 31, 23};
        int size = list.length;
        shellSort(list, size);
 
    }
}
​

* 수행 결과

 

 

 

 

[참조] C로 배우는 쉬운 자료구조, 한빛미디어, 이지영 저