4. Shell Sortting
Insertion Sorting은 N이 작을 경우와, 반정렬,정렬된상태(최선의 경우 O(N)) 소요 시간이 매우 짧다. 이를 이용한 Sorting으로 Divide and Conquor방법의 대표적인 예라고 할수 있다. 자료를 일정 부분(h)로 나누어서 각각에 대해서 insertion sorting을 하고 sorting된 전체 자료를 다시 h-1로 나누어서 각각에 대해서 insertion sorting하고 이 마지막으로 전체를 insertion sorting하는 방법이다.
예를 들어 8, 2, 9, 3, 4, 5, 7, 1 을 정렬한다면 h=3으로 하여
8,3,7 에 대해서 insertion sorting
2,4,1에 대해서 insertion sorting
9,5에 대해서 insertion sorting을 한다.
그러면 3, 1, 5, 7, 2, 9, 8, 4가 나오고 h=2로 하여
3,5,2,8에 대해서 insertion sorting
1,7,8,4에 대해서 insertion sorting을 수행한다.
그러면 2,1,3,4,5,7,8,9 가 나오고 h=1로 해서 insertion sorting하면 정렬된 자료가 나온다.
h=2까지의 단계만 봐도 꽤 많이 정렬이 된 상태라고 볼수 있다. 이런 상태면 최적의 상태 O(N)에 가까운 수행 속도를 보여주며 h에 따라서 수행 속도가 영향을 받으나 O(N(logN)^2) 정도 또는 O(N^1.25)의 수행 속도를 보여준다.
코드의 간결함, 추가적인 메모리(스택)를 사용하지 않는 등을 감안한다면 쉘 정렬은 꽤 효율적인 알고리즘이다.
한가지 단점은 안정성(Stability)가 없다는 것이다.특정 간격에 나타나는 자료를 가지고 정렬을 하는 관계로 키 필드가 있다면 키 필드가 원래의 순서를 유지 못하게 된다
예를 들어
A 1
B 2
A 3
A 4
B 5 라는 값과 Key를 가진 자료를 A,B에 대해서 정렬한다면
안정성이 있는 정렬은
A 1
A 3
A 4
B 2
B 5 가 되는데 안정성이 없는 경우
A 3
A 1
A 4
B 5
B 2 같은 형태가 되는 것이다.
안정성이 있는 정렬로는 :bubble,insertion,merge sorting이 있으며
안정성이 없는 정렬로는:shell, selection, quick, radix정렬이 있다.
