tose33

기수(Radix) 란 데이터를 구성하는 기본 요소를 의미한다. 2진수는 0과1, 10진수는 0~9, 알파벳은 'a' ~ 'z' ... 정렬 알고리즘의 이론상 성능의 한계는 O(NlogN)이다. 그런데 기수 정렬의 시간복잡도는 O(N)으로, O(NlogN) 보다 빠를수 있는 유일한 알고리즘이다. 이렇게 빠를수 있는 이유는 비교 연산이 없고 메모리를 이용해 정렬을 하기 때문이다. LSD 기수 정렬 일반적으로 기수 정렬이라 함은 LSD (Least Significant Digit) 기수 정렬을 의미한다. LSD 기수 정렬은 말그대로 least significant digit 즉 첫 자리부터 시작 해서 정렬을 진행한다. 3자리 정수의 첫번째 자리 숫자들을 첫번째 자리를 비교해 순서대로 해당하는 기수의 큐에 넣는..