자료구조_정렬 ⑦기수 정렬

 

[1] 기수 정렬

---

(1) 기수정렬 개념

Radix 정렬

버킷 정렬 

자릿수의 값을 기준으로 정렬

사용되는 데이터 진법에 따라 버킷의 갯수가 달라짐 

10진수는 10+1 =11개 버킷 

8진수는 8+1  = 9개 버킷 

 

(2) 삽입정렬 과정 

세자리 정수로 구성된 데이터가 있으면 먼저 100의 자리의 값을 기준으로 버킷을 이용하여 정렬하고 

결과를 10의 자리값을 기준으로 정렬하고 1의 자리값을 기준으로 정렬하여 정렬을 완료한다

 

(3) 시간복잡도 O(n)