정렬: 셸 정렬 알고리즘

Algorithm : 셸 정렬 알고리즘

: 단순 삽입 정렬의 장점은 살리고 단점을 보완하여 조금 더 빠르게 정렬하는 알고리즘으로, 정렬할 배열의 요소를 그룹으로 나눠 각 그룹 별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법

 

단순 삽입 정렬 포스팅

정렬: 단순 삽입 정렬 알고리즘

 

1. 셸 정렬 알고리즘의 시간복잡도

: O(n^1.25)

 

2. 셸 정렬 알고리즘 코드

출처 : 11399번: ATM (acmicpc.net)

11399번: ATM

 

import java.util.Scanner;

class ATM {
    
    static void shellSort(int[] array, int n) {
        
        int h;
        
        for(h = 1; h < n / 9; h = h * 3 + 1)
        ;
        // h값이 서로 배수가 되면 정렬 알고리즘이 동작하지 않기 때문에 수열을 사용
        // 1부터 시작하여 3배한 값에 1을 더하는 수열
        // h의 초깃값이 너무 크면 효과가 없기 때문에 배열의 요솟수 n을 9로 나눈 값을 넘지 않도록
        
        for( ; h > 0; h /= 3) {
            
            for(int i = h; i < n; i++) {
                
                int j;
                int temp = array[i];
                
                for(j = i - h; j >= 0 && array[j] > temp; j -= h)
                    array[j + h] = array[j];
                array[j + h] = temp;
            }
            
        }
        
        sumMin(array);
        
    }
    
    static void sumMin(int[] array) {
        
        int sum = 0;
        int allSum = 0;
        
        for(int i = 0; i < array.length; i++) {
            
            sum += array[i];
            allSum += sum;
            
            System.out.println(allSum);
            
        }
        
    }
    
}

public class Main
{
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		int n;
		
		n = stdIn.nextInt();
		int[] sorting = new int[n];
		
		for(int i = 0; i < n; i++) {
		    
		    sorting[i] = stdIn.nextInt();
		    
		}
		
		ATM atm = new ATM();
		atm.shellSort(sorting, n);
	}
}