Problem Solving/Algorithm, DS
[알고리즘] 기수정렬, 계수정렬 Radix, Counting Sort (C++ 구현)
버킷정렬, 기수정렬, 계수정렬은 비교에 기반하지 않는 정렬 방법으로 시간복잡도 O(nlogn)보다 빠르게 구현하고자 제안된 정렬 알고리즘이다. 오늘은 기수정렬과 계수정렬에 대해 알아보고자 한다. 간단하니까 툭툭 치고 넘어간다. 📌 기수정렬 Radix Sort 기수정렬의 핵심은 낮은 자리에서 높은 자리로 기준을 바꾸어 가며 정렬하는 것이다. stable sort가 적용된 대표적인 정렬로 이전의 정렬 순서가 바뀌지 않는다. 실제로 정렬을 한다기보다 자릿수에 맞게 0~9까지의 버킷이 있고 이 버킷에 해당하는 자릿수를 포함한 수를 넣는 방식이다. 자리를 바꿔가며 버킷에 넣는 걸 반복하면 자동적으로 정렬이 되는 원리이다. 이때 버킷은 Queue(큐, First In First Out) 방식을 사용한다. 이때 이전..
