쉘 정렬(Shell Sort)

Algorithmday_4 정리 (2021.12.01 수요일)

쉘 정렬(Shell Sort)

• 원소의 비교 연산과 먼 거리의 이동을 줄이기 위해 몇 개의 서브 리스트로 나누어 삽입 정렬 반복 수행
• 삽입 정렬의 개념을 확대하여 일반화 시킨 정렬 방법
• 삽입 정렬의 최대 문제점은 요소들이 이동할 때 이웃한 위치로만 이동한 것
• 쉘 정렬에서는 요소들이 멀리 떨어진 위치로도 이동할 수 있기 때문에 쉘 정렬이 삽입 정렬보다 속도가 빠름.
• 정렬 방법
  • 정렬에서 사용할 간격 결정
    • 전체 원소 수 n의 1/3, 다시 이것의 1/3....
    • 간격이 작아질수록 짧은 거리를 이동하고 원소 이동이 적음
  • 첫 번째 간격에 따라 서브 리스트로 분할
    • 각 서브 리스트에 대하여 삽입 정렬 수행
  • 두 번째 간격에 따라 서브 리스트로 분할
    • 각 서브 리스트에 대하여 삽입 정렬 수행
  • 마지막 간격에 따라 서브 리스트로 분할(마지막 간격은 무조건 1이다)
    • 각 서브 리스트에 대하여 삽입 정렬 수행
    • 각 모든 원소를 1개의 그룹으로 여기는 것이고 이는 삽입 정렬 그 자체이다.

쉘 정렬 예제 코드

• ShellSort.java

public class ShellSort {
    public static void main(String[] args) {
        int [] arr = {30,60,90,10,40,80,40,20,10,60,50,30,40,90,80};
        shellSort(arr);
        System.out.println("최종");
        System.out.println(Arrays.toString(arr));
    }
    static void shellSort(int[] arr) {
        int n = arr.length;
        for(int i = n/2; i > 0; i/=2) {
            System.out.println("간격 i = " + i);
            for(int j = i; j < n; j++) { // 삽입 정렬을 위해 서브 리스트의 두 번째 값을 가지고 비교
                int index = j - i;
                int temp = arr[j];
                // 삽입 정렬 수행
                while (index >= 0 && arr[index] > temp) {
                    arr[index+i] = arr[index];
                    index -= i;
                }
                arr[index + i] = temp;
            }
            // 각 간격마다 정렬 결과
            System.out.println(Arrays.toString(arr));
            System.out.println();
        }
    }
}