쉘 정렬

1. 쉘 정렬

package myTest4;
 
import java.util.Scanner;
 
public class ShellSort {
    
    static void shellSort(int[] a, int n){
        for(int h= n/2; h>0; h /= 2){
            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("셀 정렬(버전 1)");
        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();
        }
        
        shellSort(array, arrayLength);        
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.println("array["+i+"]:" + array[i]);
        }
        System.out.println();
    }
}

쉘 정렬 결과

셀 정렬(버전 1)
배열의 길이: 6
array[0]:6
array[1]:5
array[2]:4
array[3]:3
array[4]:2
array[5]:1
354621
324651
321654
231654
123654
123654
123564
123456
오름차순 정렬완료
array[0]:1
array[1]:2
array[2]:3
array[3]:4
array[4]:5
array[5]:6

2. 증분값 h를 변경한 쉘정렬 

package myTest4;
 
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();
    }
}

증분값 h를 변경한 쉘정렬 결과

셀 정렬(버전 2)
배열의 길이: 6
array[0]:6
array[1]:5
array[2]:4
array[3]:3
array[4]:2
array[5]:1
564321
456321
345621
234561
123456
오름차순 정렬완료
array[0]:1
array[1]:2
array[2]:3
array[3]:4
array[4]:5
array[5]:6