기수 정렬

기수 정렬은 정렬 알고리즘 중 별종입니다. 두 값 중 어느 쪽이 큰지 한 번도 묻지 않습니다. 수를 한 자리씩 읽고, 버킷 10개를 사용해 한 번에 한 자리씩 정렬합니다. 이 아이디어는 컴퓨터보다 오래되었습니다. 천공 카드 분류기가 바로 이렇게 동작했습니다.

0부터 9까지 라벨이 붙은 버킷 10개가 한 줄로 놓여 있고 그 위에 목록의 막대가 있으며, 값 하나가 마지막 자리에 해당하는 버킷으로 떨어지는 모습
0부터 9까지 라벨이 붙은 버킷 10개가 한 줄로 놓여 있고 그 위에 목록의 막대가 있으며, 값 하나가 마지막 자리에 해당하는 버킷으로 떨어지는 모습

아이디어

먼저 일의 자리만으로 수를 정렬합니다. 다음에 십의 자리로 정렬하되, 십의 자리가 같은 수들은 첫 번째 패스가 정한 순서를 유지하게 합니다. 그다음 같은 방식으로 백의 자리로 정렬합니다. 마지막 패스가 끝나면 목록이 정렬됩니다. 백의 자리가 먼저 순서를 정하고, 백의 자리가 같은 수들은 이미 십의 자리 순서로, 거기서도 같은 수들은 일의 자리 순서로 놓여 있기 때문입니다.

버킷으로 하는 한 번의 패스

각 패스는 숫자 0부터 9까지 하나씩, 버킷 10개를 씁니다. 목록을 처음부터 끝까지 훑으며 각 수를 그 숫자의 버킷으로, 이미 들어 있는 수들 뒤에 옮깁니다. 그런 다음 버킷 0부터 순서대로 버킷을 비워 목록으로 되돌립니다. 목록 순서대로 수를 옮기고 버킷 맨 뒤에 붙이는 것이 패스를 안정적으로 만듭니다. 이 앱은 먼저 숫자별로 수의 개수를 세므로, 버킷을 한 줄에 나란히 두고 각 버킷이 앞 버킷 바로 뒤에서 시작하게 할 수 있습니다. 이것이 한 자리에 대한 계수 정렬입니다.

예시

170, 45, 75, 90, 802, 24, 2, 66을 예로 들어 봅시다. 일의 자리로: 170, 90, 802, 2, 24, 45, 75, 66. 십의 자리로: 802, 2, 24, 45, 66, 170, 75, 90. 십의 자리가 둘 다 0인 802와 2는 첫 번째 패스의 순서를 유지합니다. 백의 자리로: 2, 24, 45, 66, 75, 90, 170, 802. 수 8개에 패스 세 번, 읽은 자릿수 24개와 이동 48번, 그리고 비교는 한 번도 없습니다.

얼마나 빠를까?

각 패스는 모든 수의 한 자리를 읽고 모든 수를 두 번 옮기므로, d자리 수 n개에 대한 작업량은 n · d에 비례해 늘어납니다. 비교 정렬은 최악의 경우 적어도 약 n log₂ n번 비교해야 합니다. 가능한 순서 n!가지를 예/아니요 질문 하나씩으로 구별해야 하기 때문입니다. 기수 정렬은 그런 질문을 하지 않으므로 이 한계에 묶이지 않습니다. 1,000 미만의 수 100만 개처럼 짧은 키가 많을 때, 패스 세 번은 비교 정렬에 필요한 약 2000만 번의 비교보다 훨씬 적은 작업입니다. 키가 길거나 값이 적으면 이 장점은 사라집니다.

LSD와 MSD, 그리고 역사

여기서 보여 주는 방식은 최하위 자리(LSD)부터 시작합니다. 반대로 최상위 자리부터 시작하는 방식(MSD)은 첫 자리로 목록을 버킷에 나누고 각 버킷을 따로 정렬하므로, 길이가 다른 문자열에 알맞습니다. 기수 정렬은 1890년 미국 인구 조사에 쓰인 Herman Hollerith의 집계기 뒤에 등장한 천공 카드 분류기로 거슬러 올라갑니다. 분류기는 한 열의 구멍 위치에 따라 각 카드를 주머니 10개 중 하나에 떨어뜨렸고, 작업자는 마지막 열부터 시작해 열마다 카드 묶음을 한 번씩 통과시켰습니다.

컴퓨터 역사 박물관의 홀러리스 천공 카드 집계기, 1890년 미국 인구 조사에 쓰인 종류. 조작원은 카드 한 벌을 열마다 한 번씩 분류기에 넣었고, 이것이 기수 정렬의 조상이다.
컴퓨터 역사 박물관의 홀러리스 천공 카드 집계기, 1890년 미국 인구 조사에 쓰인 종류. 조작원은 카드 한 벌을 열마다 한 번씩 분류기에 넣었고, 이것이 기수 정렬의 조상이다.

직접 해 보기

앱을 열고 ‘단계’를 누르세요. 각 패스는 먼저 자릿수를 세어 목록 아래 줄에 버킷 0~9의 자리를 잡습니다. 그런 다음 수가 하나씩 자기 버킷에 떨어지고, 사용 중인 버킷이 강조 표시되며, 다시 복사됩니다. 위의 예처럼 999 이하의 숫자를 직접 입력하면 세 번의 패스를 모두 볼 수 있습니다.

자주 묻는 질문

기수 정렬의 시간 복잡도는?

고정된 기수에서 d자리 키 n개에 대해 O(n · d)이며, 여기에 패스마다 버킷 비용이 더해집니다. 버킷이 들어갈 버퍼를 위해 O(n)의 추가 메모리가 필요합니다.

기수 정렬은 안정적인가요?

LSD 기수 정렬은 안정적이어야 합니다. 모든 패스가 같은 숫자를 가진 값을 들어온 순서대로 유지하기 때문에 동작하는 방식입니다. 따라서 최종 결과도 안정적입니다.

기수 정렬로 음수나 소수도 처리할 수 있나요?

바로는 안 되지만, 방법이 있습니다. 음수를 옮겨 모두 양수로 만들거나, 음수만 따로 정렬한 뒤 뒤집습니다. 부동소수점 수는 간단한 변환을 거치면 비트 패턴으로 정렬할 수 있습니다.

왜 10진법을 쓰나요?

따라가기 쉬워서입니다. 컴퓨터는 보통 한 번에 8비트나 16비트씩 정렬하므로, 32비트 수는 패스 네 번이나 두 번이 걸리고 버킷은 256개나 65,536개입니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

기수 정렬 해 보기