[java] 자바에서 쉘 정렬 구현하기

15 Dec 2023

java

쉘 정렬(Shell sort)은 삽입 정렬의 개선된 버전으로, 배열을 일정한 간격으로 나누어 부분 리스트를 만든 후, 각 부분 리스트를 삽입 정렬하는 방식으로 정렬 알고리즘입니다. 이를 통해 삽입 정렬보다 빠른 정렬 속도를 가지고 있습니다.

쉘 정렬 구현하기

public class ShellSort {
    public 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 key = arr[i];
                int j = i;
                while (j >= gap && arr[j - gap] > key) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = key;
            }
        }
    }
}

쉘 정렬 코드 설명

위의 코드는 쉘 정렬을 구현한 예시입니다.

shellSort 메소드는 정수형 배열을 매개변수로 받아 쉘 정렬을 수행합니다.
gap 변수를 이용하여 배열을 일정한 간격으로 나누어 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬하는 과정을 반복합니다.

위의 코드는 오름차순으로 정렬하는 예시이며, 내림차순으로 정렬하고 싶다면 arr[j - gap] < key와 같이 부등호의 방향을 바꿔주면 됩니다.

쉘 정렬 구현하기

쉘 정렬 코드 설명

참고 자료