셸 정렬

단순 삽입 정렬은 삽입 위치가 현재 위치에서 멀수록 연산이 멀어진다는 단점이 있습니다. 이 단점을 보완한 정렬방식이 셸 정렬입니다.

---

1. 셸 정렬

셸 정렬은 정렬할 배열의 요소를 몇개의 그룹으로 나누어 각 그룹으로 단순 삽입 정렬을 하고 그룹을 합쳐나가며 정렬을 하는 방식입니다. 그룹으로 나눌 때 h칸 만큼 떨어진 요소끼리 모아 h개의 그룹으로 나누어 정렬방식을 'h-정렬' 이라고 합니다. 셸 정렬의 시간 복잡도는 최선일 경우의 O(n)과 최악일 경우의 O(n^2)의 평균인 O(n^1.5)입니다.

다음과 같은 8개의 요소를 가진 배열을 가지고 셸 정렬을 해보겠습니다.

3

8

1

4

9

6

2

5

 

우선 4칸씩 떨어진 요소 그룹 4개로 4-정렬을 해보겠습니다. 같은 색으로 묶인 각 그룹에 대해 큰 수는 뒤로 작은 수는 앞으로 가도록 정렬합니다.

이렇게 4-정렬이 종료되었습니다. 그러면 이제 2칸씩 떨어진 요소 그룹 2개에 대해서 2-정렬을 해보겠습니다. 마찬가지로 각 그룹에서 작은 숫자들이 앞으로 가도록 만들어 줍니다.

 

2-정렬까지 수행하니 제법 그럴듯하게 정렬이 되었습니다. 마지막으로 1칸씩 떨어진 그룹 1개, 즉 전체 배열에 대해서 1-정렬을 수행하면 정렬이 완료됩니다.

 

이렇게 정렬이 완료되었습니다 길이 8의 배열에 대해서 4-정렬에서 4번의 정렬, 2-에서 2번의 정렬, 1-정렬에서 1번의 정렬, 총 7회의 정렬을 통해 정렬을 수행했습니다. 이는 단순 삽입 정렬의 n^2/2회 (길이 8인 배열에 대해서는 32회)의 정렬보다 작은 횟수의 교환을 통해 수행되어 더 빠른 정렬 방식임을 알 수 있습니다.

 

 

2. 셸 정렬 구현

export const shellSort = arr => {
    //h-정렬을 결정하는 횟수 = 배열길이2, 이후로는 h/2를 해서 결정
    for (let h = arr.length / 2; h > 0; h /= 2) {
        for (let i = h; i < arr.length; i++) {
            let j;
            let temp = arr[i];

            for (j = i - h; j >= 0 && arr[j] > temp; j -= h) {
                arr[j + h] = arr[j];
            }
            arr[j + h] = temp;
        }
    }

    return arr;
};

import {shellSort} from './study-code/sort/shell-sort.js';

let arr = [3, 8, 1, 4, 9, 6, 2, 5];

console.log(shellSort(arr));