기수 정렬
-
특수 정렬 알고리즘프로그래밍 기초/알고리즘 2021. 7. 21. 14:56
특수 정렬 알고리즘 두 원소를 비교하여 정렬하는 경우엔 수행 시간인 Ο(nlogn) 보다 빨라질 수 없다. 그러나 입력 값이 특수한 성질을 만족하는 경우 이러한 한계를 넘을 수 있는 알고리즘이 존재한다. 기수 정렬 입력이 모두 k 이하의 자릿수를 가진 자연수인 경우 사용할 수 있는 정렬 방법으로 Θ(n) 이 소요되는 알고리즘이다. 기수 정렬 알고리즘 RadixSort(A[], n, k) { for i ← 1 to k { i 번째 자리수에 대해 A[1...n]을 안정성을 유지하면서 정렬한다. } } ※ 안정성을 유지한다는 것은 비교한 결과가 같으면 자리가 유지되어야 한다는 의미이다. 계수 정렬 입력의 값이 모두 Ο(n)을 넘지 않는 경우 사용할 수 있는 정렬 방법으로 Θ(n) 이 소요되는 알고리즘이다. 계..