[Java] 쉘 정렬 (Shell Sort)

쉘 정렬이란 배열을 특정 간격(gap)으로 묶어서 gap의 자리수 특정 자리수끼리 삽입 정렬 로직을 수행하는 정렬이다. 

[9, 4, 1, 7, 3, 2, 1, 5, 0, 6, 8]

gap : 4
[0, 2, 1, 5, 3, 4, 1, 7, 9, 6, 8]
gap : 2
[0, 2, 1, 4, 1, 5, 3, 6, 8, 7, 9]
gap : 1  
[0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9]

import java.util.Arrays;
 
public class ShellSort {
 
    public static void main(String[] args) {
 
        int[] arr = {9, 4, 1, 7, 3, 2, 1, 5, 0, 6, 8};
        int len = arr.length;
 
        int temp = 0;
        int gap = len;
        for (; gap > 1;) {
            gap = (gap / 3) + 1;
            System.out.println("gap : " + gap);
            for (int i = 0; i < gap; i++) {// gap 만큼 반복한다
                //삽입 정렬 로직
                for (int j = i + gap; j < len; j += gap) {
                    /*
                    i : 묶음을 구분하기 위한 값
                    j : 삽입 정렬 종료 인덱스 
                     */
 
                    for (int x = i; x < j; x += gap) {
                        /*
                        x인덱스 ~ j인덱스 까지 반복하여 삽입정렬을 실행한다.
                         */
                        if (arr[x] > arr[j]) {
                            temp = arr[x];
                            arr[x] = arr[j];
                            arr[j] = temp;
                        }
                    }
                }
            }
 
            System.out.println(Arrays.toString(arr));
        }
 
    }
}