셸정렬

삽입 정렬의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘

위에서 공부한 삽입정렬 특징을 간략하게 정리하자면

• 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라진다.(장점)
• 삽입할 위치가 멀리 떨어져 있으면 이동해야 하는 횟수가 많아진다. (단점)

셸정렬 알고리즘의 순서이다.

1. 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 삽입 정렬 수행
2. 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄인다.
3. 위의 과정을 그룹의 개수가 1이 될 때까지 반복한다.

셸정렬 - 예시

셸 정렬에서 수행하는 각각의 정렬을 'h-정렬' 이라고 한다.
그림으로 바로 살펴보자.

• 최초의 배열을 4칸만큼 떨어진 요소를 모아 그룹 4개로 나누어 정렬한다.
• {8, 7}, {1, 6}, {4, 3}, {2, 5} 그룹을 정렬한다.
• 위의 정렬 방법을 '4-정렬' 이라고 한다.
• 정렬을 마친 상태는 아니지만 조금 더 정렬을 마친 상태에 가까워졌다!
  

• '4-정렬'을 마친 상태에서 2칸만큼 떨어진 요소를 모아 그룹 2개로로 나눈다.
• {7, 3, 8, 4}, {3, 4, 7, 8} 그룹을 정렬한다.
• 위의 정렬 방법을 '2-정렬' 이라 한다.
  

2-정렬 까지 마치고 나면 배열은 좀 더 정렬된 상태에 가까워 진다.
마지막으로 '1-정렬' 인 일반적인 삽입정렬을 수행한다.

정리하면, 정렬되지 않은 상태의 배열에 대해 단순하게 삽입정렬을 적용하는 것이 아니라
'4-정렬', '2-정렬' 처럼 조금이라도 정렬이 된 상태에 가까운 배열로 만든 다음 마지막 삽입정렬 을 하는 것이다.

정렬해야하는 횟수는 늘지만 전체적으로 요소 이동 횟수가 줄어들어 효율적인 정렬을 할 수 있다.

셸정렬 - Java 코드

public class ShellSortTest {

    public static void shellSort(int[] arr) {

        // h 인덱스를 기준으로 비교 시작
        // h는 현재를 반으로 나눈 기준으로 잡았다.
        // 삽입 정렬 코드와 거의 같다. 차이점은 선택한 요소와 비교하는 요소가
        // 이웃하지 않고 h 만큼 떨어져 있다.
        for (int h = arr.length / 2; h > 0; h /= 2 ) {
            for (int i = h; i < arr.length; i++) {
                int idx = i - h;
                int tmp = arr[i];

                while( (idx >= 0) && (arr[idx] > tmp) ) {
                    arr[idx + h] = arr[idx];
                    idx -= h;
                }

                arr[idx + h] = tmp;
            }
        }
    }

    public static void main(String[] args) {

        int[] arr = {3, 1, 2, 6, 7 , 5, 4};

        shellSort(arr);

        System.out.println(Arrays.toString(arr));
    }

}

셸정렬 특징

• 장점
  • 연속적이지 않은 리스트의 자료 교환이 일어나면 더 큰 거리를 이동한다.
    • 교환되는 요소들이 삽입정렬보다 최종위치에 있을 가능성이 더 높아진다.
  • 삽입정렬의 장점은 취하고 단점을 보완해서 삽입정렬보다 성능이 좋다.
  • 시간복잡도
    • 최선일 때는 삽입정렬과 동일한 O(n)
    • 평균 O(n1.5)
    • 최악 O(n2)
• 단점
  • h 간격을 잘못 설정한다면 성능이 굉장히 안 좋아질수 있다. -> O(n2)
    • 보통 전체에서 h/2를 하지만 이보다 h/3 + 1 이 더 빠르다.

References

• 셸정렬-위키백과
• https://gmlwjd9405.github.io/2017/10/01/basic-concepts-of-development-algorithm.html
• https://yabmoons.tistory.com/250
• 보요 시바타, 『자료구조와 함께 배우는 알고리즘 입문』, 이지스퍼블리싱(2018)
• 모든 이미지는 직접 그림