Quick Sort

위키백과 사전에 나온게 가장 심플하고 이해하기 쉽다. Quick Sort 는 A.R 호어 가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. Quick Sort 는 n 개의 데이터를 정렬할 때, 최악의 경우 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n) 번의 비교를 수행한다.Quick Sort 의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계 되어 있고 (그 이유는 메모리 참조가 지역화 되어 있기 때문에 CPU, 캐시의 히트 율이 높아지기 때문이다...뭔소리래..) , 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다.때문에 일반적인 경우 퀵 정렬은 다른 O(n log..

2014.09.02