- 사용 중인 버킷
- 방금 이동함
- 다시 복사됨
- 제자리
기수 정렬
기수 정렬은 정수를 두 개씩 비교하지 않고 정렬합니다. 먼저 일의 자리로, 다음에 십의 자리로, 그다음 백의 자리로 목록을 정렬하며, 매번 값을 버킷 10개로 옮긴 뒤 순서대로 다시 복사합니다. 목록 아래 줄에서 버킷이 한 번에 하나씩 채워지는 모습을 보고, 목록이 점점 더 많은 자릿수로 정렬되는 과정을 확인하세요. ‘재생’을 눌러 정렬을 보거나, ‘단계’와 ‘뒤로’로 이동을 하나씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 목록 아래 줄에는 버킷 0~9가 나란히 놓여 있습니다. 타일에는 읽은 자릿수, 이동, 패스 횟수가 표시됩니다. 막대 개수와 시작 순서를 고르거나 999 이하의 숫자를 직접 입력하세요. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.
작동 원리
- 막대 개수와 시작 순서를 고르거나, 999 이하의 정수를 직접 입력해 백의 자리 패스를 보세요.
- ‘재생’을 누르거나, ‘단계’와 ‘뒤로’로 값을 하나씩 옮기세요. 단계 슬라이더를 끌면 정렬의 원하는 지점으로 이동합니다.
- 각 패스를 지켜보세요: 자릿수를 세고, 모든 값을 버킷으로 옮긴 뒤, 버킷을 다시 복사합니다.
기수 정렬의 원리
모든 수의 마지막 자리만 보고 그것으로 목록을 정렬합니다. 각 수를 들어온 순서를 유지한 채 0부터 9까지 버킷 10개 중 하나에 넣고, 버킷을 차례로 다시 복사합니다. 십의 자리와 백의 자리로도 똑같이 합니다. 각 패스는 같은 숫자를 가진 수들의 순서를 유지하므로, 그 수들 사이의 순서는 앞선 패스가 계속 정하며, 마지막 패스가 끝나면 목록 전체가 정렬됩니다.
비교가 전혀 없음
비교 정렬은 어떤 기발한 방법을 쓰든 최악의 경우 적어도 약 n log₂ n번 비교해야 합니다. 기수 정렬은 대신 자릿수를 읽어 이 한계를 피합니다. 각 패스는 모든 값의 한 자리를 읽고 모든 값을 두 번 옮기므로, 자릿수가 d개면 d번 패스하고 작업량은 n · d에 비례해 늘어납니다. 짧은 키로 된 긴 목록이라면 이득이 큽니다. 999 이하의 수 100만 개는 패스 세 번이면 되지만, 비교 정렬은 약 2000만 번 비교해야 합니다. 대신 숫자나 문자로 이루어진 키에만 쓸 수 있고, 버킷을 위한 공간이 필요합니다.
자주 묻는 질문
기수 정렬은 어떻게 동작하나요?
수를 마지막 자리로 정렬하고, 그다음 앞자리로, 이렇게 첫 자리까지 정렬합니다. 각 패스는 그 자리 숫자에 따라 순서를 유지한 채 수를 버킷 10개에 넣고 버킷을 다시 복사합니다. 가장 높은 자리에 대한 패스가 끝나면 목록이 정렬됩니다.
왜 마지막 자리부터 시작하나요?
각 패스가 안정적이기 때문입니다. 같은 숫자를 가진 수는 앞선 패스가 정한 순서를 유지합니다. 그래서 첫 자리에 대한 마지막 패스가 순서를 정하고, 같은 경우에는 이미 정렬된 자릿수가 순서를 정합니다. 이를 LSD(최하위 자리) 기수 정렬이라고 합니다.
기수 정렬이 퀵 정렬보다 빠른가요?
짧은 키가 많을 때는 그럴 수 있습니다. 작업량이 값의 개수 곱하기 자릿수에 비례하고, n log n이 붙지 않습니다. 값이 적거나, 키가 아주 길거나, 숫자로 이루어지지 않은 데이터라면 대개 퀵 정렬과 병합 정렬이 더 빠르고 간단합니다.
계수 정렬과는 어떤 관계인가요?
기수 정렬의 각 패스는 한 자리에 대한 계수 정렬입니다. 각 숫자를 가진 값이 몇 개인지 세고, 각 버킷의 시작 위치를 계산한 뒤, 값을 순서대로 그곳으로 옮깁니다.
내 숫자가 어딘가로 전송되나요?
아니요. 정렬은 브라우저에서 실행되며, 마지막 설정은 이 브라우저의 로컬 저장소에 저장됩니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동