카운팅 정렬 (1) 썸네일형 리스트형 [알고리즘] 정렬(3) - 기수 정렬, 카운팅 정렬 \(\Theta(n^2)\)와 \(\Theta(nlogn)\)이 소요되는 정렬 알고리즘들을 알아봤다. 이번에는 특수한 상황에서 사용할 수 있는 알고리즘을 살펴보겠다. 기수 정렬(Radix Sort) 기수 정렬이란 입력이 모두 k 자릿수 이하의 자연수인 경우에 사용할 수 있는 알고리즘이다. 가장 낮은 자릿수만으로 수를 정렬한 뒤, 다음 자릿수로 정렬, ... 를 반복해서 정렬된 배열을 얻는 방법이다. 이때, 같은 수라면 먼저 들어간 수가 위로 정렬된다. C++로 구현한 기수 정렬 const int PLACE_VALUE = 10; const int DIGIT = 2; void radix_sort(int* arr, int start, int end) { std::queue k[PLACE_VALUE]; // 자.. 이전 1 다음