카고짱짱짱님의 면접 결과

기수 정렬(Radix Sort)은 비교 기반이 아닌 정렬 알고리즘으로, 정수나 문자열 등 자릿수 기반으로 정렬 가능한 데이터에 대해 매우 효율적으로 동작합니다. LSB(Lowest Significant Digit) 방식과 MSB(Most Significant Digit) 방식으로 나뉘며, 가장 흔한 구현은 LSB 방식입니다.

기수 정렬은 가장 낮은 자릿수(LSB)부터 시작해 자릿수별로 정렬을 반복하는 방식으로, 정수나 문자열처럼 자릿값이 있는 데이터를 정렬할 때 사용됩니다. 이때 각 자릿수에서의 정렬은 반드시 안정 정렬이어야 이전 자릿수에서 유지된 상대적 순서가 유지되어 전체 정렬 결과가 올바르게 나옵니다.

계수 정렬(Counting Sort)은 비교 기반이 아닌 정렬 알고리즘으로, 각 값의 등장 횟수를 세어 그 정보를 기반으로 정렬된 위치를 결정합니다. 입력 값이 정수이고 값의 범위가 제한적일 때 매우 효율적으로 동작합니다. 먼저 입력 배열을 순회하며 각 숫자의 등장 횟수를 카운트하고, 누적합 배열을 만들어 정렬된 위치를 계산한 뒤, 원본 데이터를 반복하면서 결과 배열에 정렬된 값을 채워 넣습니다. 기수 정렬에서는 각 자릿수를 기준으로 데이터를 여러 번 정렬해야 하는데, 이때 안정 정렬이 반드시 필요합니다. 계수 정렬은 안정 정렬이 가능하고, 각 자릿값이 0~9처럼 작은 범위의 정수값일 때 가장 효율적으로 동작합니다. 게다가 자릿수별로 정렬할 때 비교 기반 정렬은 불필요하게 느리기 때문에, **시간 복잡도가 O(n + k)**인 계수 정렬이 최적입니다. 이처럼 계수 정렬은 고정된 자릿수 정렬에서 빠르고 안정적이며, 기수 정렬의 반복적인 서브루틴으로 매우 적합합니다.