[정렬알고리즘] - 4. 쉘 정렬(Shell Sort)

쉘정렬은 삽입정렬의 취약점을 보완하고자 나온 정렬 알고리즘인데 변위를 하나 두어서 변위 간격의 요소들을 뽑아서 삽입정렬 변위를 줄이고 다시 삽입정렬.. 이렇게 해나가다 변위가 1이 되면 삽입정렬을 하고 종료한다.
이렇게 변위를 두기 때문에 삽입정렬에 루프가 두개나 더 추가된다.
하지만 여러가지 자료에는 삽입정렬보다 뛰어난 성능 이라고 설명되어있다. 그리고 돌려봤더니 왠걸 삽입정렬 보다 한참 느렸다.
.
.
한참 헤매다가 혹시나 해서 Release 버전으로 돌렸더니..
헉 삽입정렬 보다 빠르다는 사실..! 나를 당혹케 했다 ㅋ

아래는 구현이다.
void Shell_Sort(int ary[], int nSize) { int nTmp, nIndex; //변위를 변경시키며 루프를 수행... for(int h = nSize/2; h > 0; h /= 2) { //변위사이를 루프를 돌며 수행... for(int i = 0; i < h; i++) { //h간격으로 선택된 데이터를 삽입 정렬.. for(int j = i+h; j < nSize; j+=h) { nTmp = ary[j]; nIndex = j; while(nIndex > h-1 && nTmp < ary[j-h]) { ary[nIndex] = ary[nIndex-h]; nIndex -= h; } ary[nIndex] = nTmp; } } } }

<성능 테스트>

데이터 갯수	수행 시간
10000	492
20000	1844

p.s. 위의 테스트는 Debug모드로 수행했기에 삽입정렬보다 느리게 측정되었다. Release모드시 0이다.
나중에 날잡아 Release로 모드 테스트 해봐야겠다.