07-5 셸 정렬

※ 셸 정렬(Shell Sort)

 - 일정한 간격(interval)으로 떨어져 있는 자료들끼리 크기를 비교하여 교환

 - 일정한 간격(interval)은 원소의 개수/2 를 하고 비교가 끝난 후에는 다시 간격(interval)/2를 해서 간격이 1이 될때 까지 수행한다.

 - 전체 원소에 대하여 삽입 정렬을 수행하는 것보다 부분집합으로 나누어 정렬하면 비교 연산과 교환 연산의 횟수를 줄일 수 있다.

※ 구현

Main

public class Main {

       public static void main(String args[]){

              int a[] = {69,10,30,2,16,8,31,22};

              int size = a.length;

              ShellSort ss = new ShellSort();

              System.out.println("정렬할 원소 : ");

              for(int i=0; i<a.length; i++){

                     System.out.print(" " + a[i]);

              }

              System.out.println();

              ss.shellSort(a, size);

       }

}

ShellSort

public class ShellSort {

       

       int[] a;

       

       public void shellSort(int a[], int size){

              if(this.a==null){

                     this.a=a;

              }

              

              int h = size/2;

              int temp;

              while(h >= 1){

                     for(int i=0; i < size ; i++){

                           if(i+h <= size-1){

                                  for(int j = i+h; j<=size-1; j=j+h){

                                         if(a[j-h]> a[j]){

                                                temp = a[j];

                                                a[j] = a[j-h];

                                                a[j-h]= temp;

                                         }

                                  }

                           }else{

                                  break;

                           }

                           

                     }

                     System.out.println("중간결과");

                     printA();

                     h = h/2;

              }      

              

              System.out.println("최종결과");

              printA();

       }

       public void printA(){

              for(int i=0; i<a.length; i++){

                     System.out.print(" " + a[i]);

              }

              System.out.println();

       }

}