기수 정렬(Radix Sort)
기수 정렬(radix sort)는 정렬할 원소의 키 값을 나타내는 숫자의 자리 수(10의 자리수, 1의 자리수 등)를 기초로 정렬하는 기법이다. 이는 80칼럼 punched card를 정렬시키거나 도서관 목록 카드 정렬과 같은 생활 응용에 많이 활용된다. 예를 들어 [437,123,234,578,351,625,543] 을 정렬하면 다음과 같다. 1단계(1의 자리 수 기준 정렬) : [351,123,543,234,625,437,578] 2단계(10의 자리 수 기준 정렬) : [123,625,234,437,543,351,578] 3단계(100의 자리 수 기준 정렬) : [123,234,351,437,543,578,625] 이에 따른 기수 정렬 ADL은 다음과 같다. radixSort(a[],n) for (k
2021. 10. 24.