셸 정렬(Shall sort) Java 구현

셸 정렬(Shall sort) Java 구현

셸 정렬

• 도널드 셸(D. L. Shell)이 고안해서 셸 정렬임

• 셸 정렬은 단순 삽입 정렬의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘

• 단순 삽입 정렬의 장단점
  • 장점 : 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬속도가 매우 빨라짐
  • 단점 : 삽입할 위치가 멀리 떨어져있으면 이동해야하는 횟수가 많아짐

• 정렬과정

  • h만큼 떨어진 숫자를 리스트로 묶어 삽입정렬 진행
  • h의 수를 줄여가며 1이 될 때 까지 진행

• 장점 : 수들이 어느정도 정렬이 진행되기 때문에 h가 1일때 속도가 빨라짐

• 중요 포인트 : h값을 어떻게 설정해야 하는가
  • h값이 서로 배수관계가 되면 섞이지 않는 요소가 생겨서 의미가 없어짐
  • 2로 나누기도 하지만 1부터 시작하여 3배한 값에 1을 더하는 수열을 사용한다.

구현

import java.util.Scanner;

public class ShellSortChangeHvalue {

    static void shellSort2(int[] a, int n){
        int h;
        for( h = 1; h<n/9; h=h*3+1);

        for(;h>0; h/=3){
            for(int i= h; i<n; i++){
                int j;
                int tmp = a[i];
                for(j=i-h; j>=0 && a[j] > tmp; j-=h){
                    a[j+h] = a[j];
                }
                a[j+h] = tmp;
                for(int k=0; k<n; k++){
                    System.out.print(a[k]);
                }
                System.out.println();                        
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("셀 정렬(버전 2)");
        System.out.print("배열의 길이: ");

        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];

        for(int i=0; i<arrayLength; i++){
            System.out.print("array["+i+"]:");
            array[i] = scanner.nextInt();
        }

        shellSort2(array, arrayLength);        // 배열 x를 버블 정렬 한다.
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.println("array["+i+"]:" + array[i]);
        }
        System.out.println();
    }
}

이번에 직접 구현해보려고 했지만 이해가 가지 않는 부분이 있어 추후에 추가하고자한다.

일단은 쉘정렬의 기본 원리를 알고 넘어가기 위함이었기에 일단은 여기까지만!

//이해가 어려운부분
for( h = 1; h<n/9; h=h*3+1);
//증분값의 초기값이 n/9인 이유

시간복잡도는 O(n^1.25)