[java] 셸 정렬 알고리즘

04 Dec 2023

java

셸 정렬은 비교 기반 정렬 알고리즘 중 하나로, 삽입 정렬을 기반으로 발전시킨 알고리즘입니다. 삽입 정렬과 달리 셸 정렬은 간격을 설정하여 요소를 비교하고 이동시키는 방식으로 정렬을 수행합니다. 이렇게 함으로써 요소들을 더 효율적으로 정렬할 수 있습니다.

알고리즘 동작 방식

셸 정렬 알고리즘은 다음과 같은 방식으로 동작합니다:

정렬할 배열을 길이에 따라 여러 개의 그룹으로 분할합니다. 이때 각 그룹의 요소는 일정한 간격을 가집니다. (간격은 보통 배열의 절반으로 설정합니다)
각 그룹에 대해 삽입 정렬을 수행합니다. 이때 간격만큼 떨어진 요소끼리 비교하고, 필요한 경우 위치를 조정합니다.
간격을 절반으로 줄여가며 위의 과정을 반복합니다.
간격이 1이 될 때까지 위의 과정을 반복합니다. 이때는 일반적인 삽입 정렬을 수행합니다.

예제 코드

public class ShellSort {
    public static void shellSort(int[] arr) {
        int n = arr.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int tmp = arr[i];
                int j;
                for (j = i; j >= gap && arr[j - gap] > tmp; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = tmp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 2, 7, 1};
        shellSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

위의 코드는 셸 정렬을 구현한 예시입니다. shellSort 메소드에서는 주어진 배열을 셸 정렬 알고리즘을 이용하여 정렬합니다. main 메소드에서는 예시 배열을 생성하고 셸 정렬을 수행한 후 결과를 출력합니다.

시간 복잡도

셸 정렬의 시간 복잡도는 최선, 평균, 최악의 경우 모두 O(n^2)입니다. 하지만 삽입 정렬과 비교해보면 보다 빠른 속도를 보여줍니다. 이는 간격을 줄여가며 여러 번의 정렬을 수행하기 때문입니다.

알고리즘 동작 방식

예제 코드

시간 복잡도

참고 자료