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

 

쉘 정렬 (Shell Sort )

정렬 4번째 이야기

 

쉘 정렬을 알기전에 삽입정렬(Insert Sort)를 먼저 알아야 한다.

모른다면 삽입정렬에 대해서 알고 와라~

정렬 2번째 이야기에 삽입 정렬에 대해 자세히 설명되어 있다.





그럼 쉘 정렬이 먼지 알아보자

쉘정렬은 삽입정렬의 단점을 보완한 정렬이다.






삽입정렬의 단점은

요소들이 삽입 될때 이웃한 위치로만 이동을 한다.

이동 하는 과정에서 위치가 멀리 떨어진 곳이라면

많은 이동에 대한 오버헤드가 발생한다.





그래서 도날드. L. 쉘 이라는 사람이 간격(Gap) 이라는 것을 생각한 것이다 

그래서 쉘 정렬 이 아닌가 싶다.

위의 조개사진은 무관하다. ㅋ





방법은 데이터를 일정의 간격(Gap)을 만들고

이 간격들을 각각 삽입정렬을 통하여 정렬한다.

그리고 다시 간격을 합치고

또 다른 일정의 간격으로 위의 내용을 수행하는 것이다.




위의 과정을 몇회 수행하다 보면

데이터가 정렬이 되어지는 경향을 가진다.

그리고 최종적으로 Gap 없이 삽입정렬을 수행하는 것이다.





이는 삽입정렬을 하려고 하는데

데이터의 이동에 따른 오버헤드가 많이 발생하기 때문에

 약간의 정렬 상태로 만들어 삽입정렬을 하겠다는 것으로

 이해하면 쉬울거 같다.






여기서 의문이 하나 생길것이다.

간격은 어떻게 나눠야 하는가요 ? 

이런 의문이 들것이다.

여기서 간격을 어떻게 나누냐에 따라

속도가 달라 지게 되는데





보통 우리가 배워온 알고리즘은

일정의 간격 K를 놓고

K를 반으로 줄어 들면서 ( K = K / 2) 

K 가 1이 될때 까지 수행하는 방법으로 배웠다.





여기서 말하고자 싶은것은

쉘 정렬의 실제 의미는

쉘정렬은 1/2 로 줄이면서 하는 방법이 아니라





다양한 간격으로 나누어 삽입정렬을 하고 이를 다시 합쳐 보면

 어느정도 정렬이 되어지는 경향을 가지기에

이 정렬이 되어진 것을 최종적으로

삽입정렬을 하겠다는 것이 쉘정렬의 정의라는 것이다.




하지만 이를

다른 사람에게 설명할려고 하니

K = K/2 방법이 가장 설명하기 쉬울거 같다.

괸히 책에서 K = K/2 이 방법으로 쓰여진게 아닌가 쉽다  ^^;;




자 이제 말은 어려우니

그림으로 이해 해 보자

5 -> 10 -> 7 -> 4 -> 2 -> 6 -> 3 -> 8 -> 1 -> 9
 
정렬이 있다고 하면

K = 5

5 -> 10    ->    7 -> 4    ->    2 -> 6    ->    3 -> 8    ->    1 -> 9   (Gap =  5)

5 -> 10    ->    4 -> 7    ->    2 -> 6    ->    3 -> 8    ->    1 -> 9   (삽입정렬)

5 -> 10 -> 4 -> 7 -> 2 -> 6 -> 3 -> 8 -> 1 -> 9  (합친다)




K = 3

5 -> 10 -> 7      ->     4 -> 2 -> 6    ->    3 -> 8 ->1 -> 9   (Gap =  3)

5 -> 7 -> 10      ->     2 -> 4 -> 6    ->    1 -> 3 ->8 -> 9  (삽입정렬)

5 -> 7 -> 10 -> 2 -> 4 -> 6 -> 1 -> 3 -> 8 -> 9  (합친다)



K = 1

5 -> 7 -> 10 -> 2 -> 4 -> 6 -> 1 -> 3 -> 8 -> 9 

삽입정렬 한다


이런식으로 하는 것이다.

하지만 이게 왜 빠른지 궁금할 것이다.

소량의 데이터에서는 그 차이를 느낄 수 없지만

다수의 데이터에서는 삽입 정렬과 비교 했을때

차이가 많이 나는 결과를 얻을 수 있을 것이다.

나중에 정렬간의 속도 비교를 할 건데

그때 확인하기 바란다.




시간복잡도는

최악의 경우에는 O(n^2)

평균은 O(n^1.5)라 한다.

최상은 당연히 정렬이 되어 있을 경우이다.








쉘 정렬에 대해서 도움이 되었다면 리플 &^^