[백준] 2750

https://www.acmicpc.net/submit/2750/49300262

로그인

[문제 설명]

- 셸 알고리즘 사용

 

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int length = scan.nextInt();
		
		int[] arr = new int[length];
		for(int i=0; i<length; i++) {
			arr[i] = scan.nextInt();
		}
		sort(arr, length);
        
        for(int n:arr)
            System.out.println(n);
	}//main
	
	//정렬하는 메소드
	static void sort(int[] a, int length) {
		
		//간격 (최소: 1, 최대: 배열의 길이보다 작아야 한다 + (부분집합 내 요소가 최소 2개)
		int h; 
		for(h=1; h<length/9 ;h=h*3+1);
		
		for(;h>0;h/=3) {
			
			for(int i=h; i<length; i++) { //정렬되지 않는 범위를 지정하는 변수i
				int start = a[i]; //정렬X범위의 첫 요소
				int j;
				//정렬된 범위를 지정해 이전 요소들과 비교 
				for(j=i-h; j>=0 && start<a[j]; j-=h) 
					a[j+h] = a[j];
				a[j+h] = start;
			}
		}		
	}//sort
}