기수(radix) 정렬(C/C++ 구현, 시간 복잡도)

1. 기수 정렬

기수 정렬(radix sort)은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다. 자릿수가 고정되어 있으니, 안정성이 있고(이때 데이터들 간의 상대적 순서는 보존되어야 한다.) 시간 복잡도는 O(dn)}는 가장 큰 데이터의 자리수)

 

내 해석 : 피벗을 기준으로 작은 것은 왼쪽 큰것은 오른쪽으로 정렬하며 정렬된 배열을 재귀적으로 정렬하는 알고리즘

출처 : https://ko.wikipedia.org/wiki/%EA%B8%B0%EC%88%98_%EC%A0%95%EB%A0%AC

기수 정렬 - 위키백과, 우리 모두의 백과사전

 

요구 사항

1. 배열 오름차순으로 구현

 

풀이 방법

1. 1의 자리 수 부터 배열의 처음 부터 끝까지 큐에 넣음

2. 배열의 앞쪽 부터 큐에서 제거하면서 정렬

 

3. 2의 자리 순으로 정렬(배열의 처음부터 자리에 맞는 큐에 넣음)

4. 배열의 앞쪽 부터 큐에서 제거하면서 정렬

....

제일 큰 자릿 수 까지 반복

 

시간 복잡도

1. 제일큰 자릿 수 까지 하는데 M

2. n번 반복 하며 정렬 n

O(Mn)

 

소스 코드

https://yabmoons.tistory.com/248

[ 정렬 ] 기수 정렬 (Radix Sort) (C++)