[알고리즘 정렬] 셸 정렬(Shell Sort)

  셸 정렬(Shell Sort)이란 삽입 정렬의 약점을 보완한 정렬 방식입니다. 삽입 정렬은 오름차순 정렬 기준일 때 내림차순으로 구성된 데이터에 대해서는 앞의 데이터와 하나씩 비교하며 모두 교환이 필요합니다. 셸 정렬은 이전의 모든 데이터와 비교하지 않고 일정 간격을 두고 비교합니다. 알고리즘 복잡도는 O(n^2)입니다. 간격 설정에 따라 최악의 경우 삽입 정렬과 동일할 수 있고, 일반적으로는 삽입 정렬보다 빠릅니다.

 

이미지 출처: 위키백과, 셸 정렬 항목

 

  셸 정렬 구현 코드

public class Main {
    public static void shellSort(int[] array) {
        int gap = array.length / 2;
        for (int g = gap; g > 0; g /= 2) {
            for (int i = g; i < array.length; i++) {
                int temp = array[i];
                int j = 0;
                for (j = i - g; j >= 0; j -= g) {
                    if (array[j] > temp) {
                        array[j + g] = array[j];
                    } else {
                        break;
                    }
                }
                array[j + g] = temp;
            }
        }
    }
}

  매개 변수로 배열 array를 받는 shellSort 메소드를 생성합니다.

  변수 gap을 생성합니다. array의 길이를 반으로 나눈 값을 할당합니다. 이는 일정 간격을 두고 비교하는 셸 정렬에서 일정한 간격을 의미합니다. 이 값으로 삽입 정렬을 진행할 것입니다. 셸 정렬은 삽입 정렬을 보완한 방식이므로 유사합니다.

  첫 번째 for문에서 gap부터 시작하여 gap이 0보다 큰 동안 gap을 절반으로 줄여나가면서 반복합니다.

  두 번째 for문에서 i가 g부터 array의 길이만큼 순회합니다. 현재 간격으로 배열을 삽입 정렬하는 부분입니다.

  임시 변수 temp를 생성하여 array의 i 번째 원소를 할당합니다. j는 for문 밖에서도 이용하기 위해 미리 생성했습니다.

  세 번째 for문에서 j가 i - g부터 j가 0보다 크거나 같은 동안에 j에서 g만큼 반복적으로 줄여나갑니다.

  if문에서 array의 j번째 원소가 temp보다 크다면 array의 j + g 번째 원소 위치에 array의 j번째 원소를 할당합니다.

  만약 앞선 조건을 충족하지 않는다면 정렬이 끝난 상태이므로 break를 이용하여 for문을 종료합니다.

  array의 j + g 번째 원소인 삽입 정렬 위치에 temp를 할당합니다.