쉘 정렬

[쉘 정렬에 대한 개요]

쉘 정렬은 삽입 정렬인데 영역을 나눈 후 삽입하는 보완된 삽입 정렬이다. 삽입 정렬은 레코드가 정리되어 있을 때 가장 좋은 시간 복잡도를 갖는다고 했다. 레코드가 작다면 정말 좋겠지만 레코드가 작아지는 것은 값의 손실도 동반하는 경우가 되므로 기대할 수 없다. 그렇다면 레코드를 쪼개는 것은 어떠한가?

모든 레코드가 그렇진 않겠지만, 레코드를 쪼개면 상대적으로 큰 레코드보다 정렬되어 있을 확률이 올라간다. 쉘 정렬은 이 점을 이용한다.

[작위적인 듯 하지만 1번처럼 통째로 보는 것보다 2번처럼 분할해서 보는 것이 더 정렬되어 있다.]

또한 레코드가 여러 개로 분할되어 있을 때 데이터가 더 큰 거리를 이동할 수 있다는 점도 장점이다. 위의 그림에서는 간격을 n/2로 두었기 때문에 두 개의 집합과 1개의 작은 집합이 생겼지만 Pass가 지날수록 집합의 개수는 더 많아질 수 있다. 집합의 개수가 많이 나뉠수록 더 오래 걸려야 하겠지만 이전 단계에서 미리 정렬을 했기 때문에 효율적인 정렬 시간을 갖게 된다.

위의 예제를 정렬해보자면,

(실수긴 한데 원래는 1, 6, 9를 비교해야 한다. 하지만 우연의 일치로 9가 맨 마지막에 가는 것이 맞으므로 그림에서는 생략한다.)

위처럼 정렬했다면 Pass1이 끝난 것이다.

Pass2 때는 4개가 한 레코드가 아닌 2개가 한 레코드가 되도록 잡아서 위처럼 비교하면 된다.

Pass2에서는 4와 6의 위치가 바뀌는 것으로 끝날 것이다.

Pass3에서는 1개가 한 레코드가 되도록 잡는다.

이 단계에서 4와 5의 위치가 바뀌게 되어 최종적인 정렬이 끝나게 된다.

(모든 Pass를 다 그리고 싶었으나 시간적 여유도 없고 핵심은 Pass 1에서 모두 보여줬을 것이라 생각하므로 생략하였다.)

쉘 정렬의 시간복잡도는 O(n)에서 O(n^2) 사이이다.