퀵 정렬, 기수 정렬

비교 연산 횟수

 O(nlog2n)

 최악의 경우 O(n2) 이지만

다른 O(nlog2n) 인 알고리즘보다 빠른 것으

로 알려져 있음.

 퀵 정렬의 장점

 데이터 이동 횟수가 적음.

 별도의 메모리 공간이 필요 없음

​

 특징

 정렬순서의 앞서고 뒤섬을 비교하지 않는다.

 정렬 알고리즘의 한계로 알려진 O(nlog2n)을 뛰어 넘

을 수 있다.

 적용할 수 있는 대상이 매우 제한적이다. 길이가 동일한

데이터들의 정렬에 용이하다!

 용어

 기수(radix): 주어진 데이터를 구성하는 기본 요소(기호)

 버킷(bucket): 기수의 수에 해당하는 만큼의 버킷을 활

용한다.

 방법

 단순히 버킷에 넣고 빼면 됨.

 즉 정렬의 과정에서 데이터간 비교가 발생하지 않음.

​