기수 정렬 (Radix Sort)

개념
레코드를 비교하지 않고 준비된 버킷을 이용하여 정렬하는 방법

I.  기수 정렬 (Radix Sort)의 개요

  가.  기수 정렬의 정의

- 레코드를 비교하지 않고 준비된 버킷을 이용하여 정렬하는 방법

 

나.  기수 정렬의 특징

- O (n log2 n) 이라는 이론적인 하한선을 깰 수 있는 유일한 방법

- 시간 복잡도 : O(kn)  k : 버킷 수

- 정렬 레코드 타입 제한

 

Ⅱ. 기수 정렬의 개념 및 사례

  가. 기수 정렬의 개념

 

 

 

 

 

 

 

 

   나. 기수 정렬 사례 (Sorting a sequence of 4-bit integers)

댓글