[자바] 셸 정렬(Shell Sort)

셸 정렬

셸 정렬은 단순 삽입 정렬을 보완하여 좀 더 빠르게 정렬하는 알고리즘입니다.

단순 삽입 정렬은 아래의 포스팅을 참고해주시길 바랍니다.
2022.01.22 - [Algorithm/Theory] - [자바] 단순 선택 정렬과 단순 삽입 정렬

[자바] 단순 선택 정렬과 단순 삽입 정렬

아래는 단순 삽입 정렬을 장점과 단점입니다.

1. 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 빠릅니다.(장점)
2. 삽입할 위치가 멀리 떨어져 있으면 이동해야 하는 횟수가 많아집니다.(단점)

셸 정렬을 단순 삽입 정렬의 단점을 보완하기 위해 먼저 배열을 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행합니다. 그룹별로 단순 삽입 정렬을 수행하게 되면 이동해야 하는 횟수가 감소하므로 단순 삽입 정렬의 단점을 보완할 수 있습니다. 그 후에 그 그룹들을 합치면서 정렬을 반복하게 되면 정렬을 마친 상태에 가까워지면서 단순 삽입 정렬의 장점을 살릴 수 있습니다.

8개의 배열로 예를 들어보겠습니다.
먼저 배열을 4칸 떨어진 요소를 그룹으로 묶어서 정렬합니다.

앞의 4-정렬을 마친 상태에서 2칸 떨어진 요소끼리 그룹으로 묶어 2-정렬을 실시합니다.

이렇게 작업이 끝난 배열은 정렬된 상태에 가까워집니다. 마지막으로 1-정렬을 적용하면 단순 삽입 정렬의 장점을 살려 정렬을 마치게 됩니다.

위의 내용으로 코드를 구현해보겠습니다.

package shellsort; 

public class ShellSort_v1 { 
	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 temp = a[i]; 
                 for (j = i - h; j >= 0 && a[j] > temp; j -= h) { // 떨어져있는 만큼 이동하여 교환
                	 a[j + h] = a[j]; } a[j + h] = temp;
                 }
         }
    } 
}

위의 내용에서는 요소들 사이의 간격은 매번 N / 2 감소시켜 마지막에 1이 되면 정렬을 마칩니다.
아래와 같이 N / 2 감소시켜 그룹별로 정렬을 한다면 두 그룹의 요소 [7, 3, 8, 4], [1, 2, 6, 5]는 섞이지 않아서 비효율적이게 됩니다. 따라서 배열 그룹을 효율적으로 나누는 요소의 간격이 필요합니다.

요소의 간격이 8, 4, 2, 1일때는 서로가 배수이기 때문에 다음 그룹에서도 섞이지 않습니다. 따라서 요소의 간격이 서로 배수가 되지 않는다면 효율적인 그룹별 정렬을 기대할 수 있을 것입니다.
아래처럼 1부터 시작하여 3배 한 값의 1을 더한 수열을 사용하면 효율적인 결과를 얻을 수 있습니다.

h = .. 121, 40, 13, 4, 1

간격이 너무 크면 효율적이지 않게 되기 때문에 배열의 크기를 9로 나눈 값을 넘지 않도록 정해야 합니다.
그 후 h값을 3으로 나누어가며 마지막인 1까지 정렬을 실시합니다.

package shellsort; public class ShellSort_v2 {
	static void shellSort(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 temp = a[i];
                    for(j = i - h; i >= 0 && a[j] > temp; j -= h) {
                    	a[j + h] = a[j]; 
                    }
                    
                    a[j + h] = temp;
             } 
        }
   } 
}