셸 정렬 (Shell Sort)

특징

• 삽입 정렬의 약점을 보완한 정렬 방식
  - 삽입 정렬의 약점
  • 오름차순 정렬 기준, 내림차순으로 구성된 데이터에 대해서는 앞의 데이터와 하나씩 비교하며 모두 교환 필요
• 이전의 모든 데이터와 비교하지 않고 일정 간격을 두어 비교
• O(n^2)
  • 간격 설정에 따라 Worst Case는 삽입 정렬과 동일
  • 일반적인 분포의 데이터는 삽입 정렬에 비해서 빠르다

정렬 과정

1)
2)

소스코드

// 셸 정렬

import java.util.Arrays;

public class Main3 {

    public static void shellSort(int[] arr) {
        // 초기 간격
        int gap = arr.length / 2;

        // 초기 간격부터 간격 반씩 줄여가면서 진행
        for (int g = gap; g > 0; g /= 2) {
            for (int i = g; i < arr.length; i++) {
                int tmp = arr[i];

                int j = 0;
                for (j = i - g; j >= 0; j -= g) {
                    if (arr[j] > tmp) {
                        arr[j + g] = arr[j];
                    } else {
                        break;
                    }
                }
                arr[j + g] = tmp;
            }
        }
    }

    public static void main(String[] args) {
        // Test code
        int[] arr = {10, 32, 52, 27, 48, 17, 99, 56};
        shellSort(arr);
        System.out.println("셸 정렬: " + Arrays.toString(arr));
    }
}