2010.05.20 13:34
 


쉘 정렬 (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)라 한다.

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








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





Posted by 차출발 차출발

댓글을 달아 주세요

  1. BlogIcon Flaskl 2012.02.09 13:50  댓글주소  수정/삭제  댓글쓰기

    안녕하세요?

    궁금한것이 생겨 댓글 남깁니다.

    퀵정렬의 시간복잡도가 O(n^2) 이던데 이 쉘정렬이 평균적으로 퀵정렬 보단 빠르다는것인가요?

    • BlogIcon 차출발 차출발 2012.02.09 14:45 신고  댓글주소  수정/삭제

      퀵정렬과 쉘정렬의 차이를 본다면 아래와 같습니다.

      최선의경우 평균의 경우 최악의 경우
      쉘 정렬 O(n) O(n^1.5) O(n^1.5)
      퀵 정렬 O(nlog2n) O(nlog2n) O(n^2)

      퀵정렬의 경우 최악의 경우가 O(n^2)이고
      쉘정렬의 경우에는 O(n^2) 입니다.
      최악의 경우 쉘정렬이 더 빠르다는 거죠
      하지만 여기서 빠르다는 것은 데이터의 량과 환경에 따라 매번 다르게 나타날 수 있습니다.

      평균적으로 빠른 정렬을 찾으신다면
      평균적으로도 O(n)인 정렬도 있습니다.
      해시의 방법을 이용하는 카운팅정렬이라고 하는

      하지만 중요한것은 어떤 정렬이 빠르다가 아니라
      자신이 사용하려는 상황에 맞는 최선의 정렬을 선택하는게 중요한 것입니다.
      그러기 때문에 가장 빠른 정렬이란 개념은 없습니다.^^

    • BlogIcon Flask 2012.02.09 17:53 신고  댓글주소  수정/삭제

      우와 답변 감사드립니다.

  2. 쉘정렬 2014.09.14 03:28  댓글주소  수정/삭제  댓글쓰기

    새벽에 쉘정렬 이해가 안되서 보았는데 잘봤습니다 이해가 잘되네요