정렬알고리즘_쉘정렬

쉘정렬

삽입정렬은  정렬된 배열에 대해서는 매우 뛰어난 성능을 보이지만 그렇지 않은 경우에는 속도가 매우 느리다

ex) 역순 배열의 경우 제일 작은 키값이 제일 뒤에 있으므로 N번의 비교와 이동을 해야한다.

 

 

 

이 문제를 해결하기 위해 h만큼의 간격으로 떨어진 레코드를 삽입하는 정렬

4중 루프가 된 것을 제외하고는 삽입 정렬과 비슷하다.

쉘 정렬의 개선

h = (h-1)/3은 풀어쓰면 h = h/3 -1/3이 되며 1/3으로 취급하기 때문에 h = h/3

<결과>

 

 

쉘정렬은 O(NlogN)을 가지는 알고리즘들에 비해서는 속도면에서는 약간 떨어지지만 10,00이하의 자료 정도라면 쉘 정렬이 오히려 더 빠를 수가 있다.

O(NlogN)을 가지는 다른 알고리즘처럼 추가적인 메모리가 필요 하지 않는다.

 

학습참고 : C로배우는 알고리즘