[Sort] 셸 정렬 (Shell Sort)

소개

• 삽입정렬의 단점을 보완하고자 나온 셸 정렬이다.
• 간격(gap) 에 맞추어 삽입정렬을 하는 정렬이다.
• O(n2)의 시간복잡도를 가지지만 삽입정렬보단 효율적이다.

 

동작원리

• 배열의 길이 / 2 를 gap 으로 설정
• 첫번째 인덱스 부터 gap에 맞는 요소들을 삽입 정렬 진행
• 위의 순서 반복

 

구현 코드

public static int[] sort(int[] nums) {
    int length = nums.length;

    for (int gap = length / 2; gap > 0; gap /= 2) {
        for (int startIndex = 0; startIndex < gap; startIndex++) {
						insertionSort(nums, startIndex, gap);
        }
    }
    return nums;
}

private static void insertionSort(int[] nums, int startIndex, int gap) {
    for (int i = startIndex + gap; i < nums.length; i += gap) {
        int temp = nums[i];
        int j;
        for (j = i - gap; j >= 0 && nums[j] > temp; j -= gap) {
            nums[j + gap] = nums[j];
        }
        nums[j + gap] = temp;
    }
}