퀵 정렬 역시 동작 방식에 대해서 정확하게 이해하도록 합시다. 심심하신 분들은 전에 적어드린 버블 정렬 공식에 임의의 숫자를 적어서 넣어보고 자신의 CPU를 기준으로 얼마나 많은 시간이 걸릴지 계산을 해보신 분들도 계실겁니다. 당연히 굉장히 낮은 숫자가 나왔을텐데, 그 1/1000 단위의 숫자를 줄이기 위해서 얼마나 많은 노력들을 하고 있는지 아신다면 그렇게 생각하지 않을겁니다.


위의 이미지는 위키의 자료를 참고하였으며, 링크는 아래와 같습니다.
http://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

위키의 자료가 워낙 잘 되어있어서 사실 그 글을 보아도 무방하다고 판단합니다.


우선 위의 이미지를 보면 퀵 소팅이라는 것이 어떠한 방식으로 동작하는지 확실하게 이해를 하셨으리라 생각합니다. 우선 임의의 난수의 분포에 대하여 랜덤한 수 하나를 골라서 잡습니다. 그리고 이를 기준으로 큰 수와 그렇지 않은 수, 2가지로 나눕니다. 그 중 하나의 집합에 대하여 특정 수를 하나 고르고, 이를 기준으로 다시 그보다 큰 수와 작은 수를 나누어가면서 정렬을 하는 방식입니다. 이해가 정확하게 되지 않으신다면, 이해가 될 때까지 위의 이미지를 살펴보세요. 정말 완벽한 설명을 하고 있는 그림입니다.

그렇다면 퀵 정렬이 정렬을 하는데 들어가는 시간에 대해서 알아보도록 하겠습니다. 이는 크게 3가지로 분류할 수 있습니다.

* 최선의 경우


* 최악의 경우


* 평균의 경우


우리는 그저 최선의 경우만 알고 계시면 될듯 합니다. (물론 그게 최선의 경우라는 것도 기억하고 있어야 합니다. -_-)
저작자 표시 비영리 변경 금지
신고
by 가우초 2011.09.28 21:41
| 1 2 3 4 5 6 ··· 11 |