읽은 자릿수
이동
패스

  • 사용 중인 버킷
  • 방금 이동함
  • 다시 복사됨
  • 제자리

기수 정렬 자세히 알아보기

기수 정렬

기수 정렬은 정수를 두 개씩 비교하지 않고 정렬합니다. 먼저 일의 자리로, 다음에 십의 자리로, 그다음 백의 자리로 목록을 정렬하며, 매번 값을 버킷 10개로 옮긴 뒤 순서대로 다시 복사합니다. 목록 아래 줄에서 버킷이 한 번에 하나씩 채워지는 모습을 보고, 목록이 점점 더 많은 자릿수로 정렬되는 과정을 확인하세요. ‘재생’을 눌러 정렬을 보거나, ‘단계’와 ‘뒤로’로 이동을 하나씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 목록 아래 줄에는 버킷 0~9가 나란히 놓여 있습니다. 타일에는 읽은 자릿수, 이동, 패스 횟수가 표시됩니다. 막대 개수와 시작 순서를 고르거나 999 이하의 숫자를 직접 입력하세요. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.

작동 원리

  1. 막대 개수와 시작 순서를 고르거나, 999 이하의 정수를 직접 입력해 백의 자리 패스를 보세요.
  2. ‘재생’을 누르거나, ‘단계’와 ‘뒤로’로 값을 하나씩 옮기세요. 단계 슬라이더를 끌면 정렬의 원하는 지점으로 이동합니다.
  3. 각 패스를 지켜보세요: 자릿수를 세고, 모든 값을 버킷으로 옮긴 뒤, 버킷을 다시 복사합니다.

기수 정렬의 원리

모든 수의 마지막 자리만 보고 그것으로 목록을 정렬합니다. 각 수를 들어온 순서를 유지한 채 0부터 9까지 버킷 10개 중 하나에 넣고, 버킷을 차례로 다시 복사합니다. 십의 자리와 백의 자리로도 똑같이 합니다. 각 패스는 같은 숫자를 가진 수들의 순서를 유지하므로, 그 수들 사이의 순서는 앞선 패스가 계속 정하며, 마지막 패스가 끝나면 목록 전체가 정렬됩니다.

비교가 전혀 없음

비교 정렬은 어떤 기발한 방법을 쓰든 최악의 경우 적어도 약 n log₂ n번 비교해야 합니다. 기수 정렬은 대신 자릿수를 읽어 이 한계를 피합니다. 각 패스는 모든 값의 한 자리를 읽고 모든 값을 두 번 옮기므로, 자릿수가 d개면 d번 패스하고 작업량은 n · d에 비례해 늘어납니다. 짧은 키로 된 긴 목록이라면 이득이 큽니다. 999 이하의 수 100만 개는 패스 세 번이면 되지만, 비교 정렬은 약 2000만 번 비교해야 합니다. 대신 숫자나 문자로 이루어진 키에만 쓸 수 있고, 버킷을 위한 공간이 필요합니다.

자주 묻는 질문

기수 정렬은 어떻게 동작하나요?

수를 마지막 자리로 정렬하고, 그다음 앞자리로, 이렇게 첫 자리까지 정렬합니다. 각 패스는 그 자리 숫자에 따라 순서를 유지한 채 수를 버킷 10개에 넣고 버킷을 다시 복사합니다. 가장 높은 자리에 대한 패스가 끝나면 목록이 정렬됩니다.

왜 마지막 자리부터 시작하나요?

각 패스가 안정적이기 때문입니다. 같은 숫자를 가진 수는 앞선 패스가 정한 순서를 유지합니다. 그래서 첫 자리에 대한 마지막 패스가 순서를 정하고, 같은 경우에는 이미 정렬된 자릿수가 순서를 정합니다. 이를 LSD(최하위 자리) 기수 정렬이라고 합니다.

기수 정렬이 퀵 정렬보다 빠른가요?

짧은 키가 많을 때는 그럴 수 있습니다. 작업량이 값의 개수 곱하기 자릿수에 비례하고, n log n이 붙지 않습니다. 값이 적거나, 키가 아주 길거나, 숫자로 이루어지지 않은 데이터라면 대개 퀵 정렬과 병합 정렬이 더 빠르고 간단합니다.

계수 정렬과는 어떤 관계인가요?

기수 정렬의 각 패스는 한 자리에 대한 계수 정렬입니다. 각 숫자를 가진 값이 몇 개인지 세고, 각 버킷의 시작 위치를 계산한 뒤, 값을 순서대로 그곳으로 옮깁니다.

내 숫자가 어딘가로 전송되나요?

아니요. 정렬은 브라우저에서 실행되며, 마지막 설정은 이 브라우저의 로컬 저장소에 저장됩니다.

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

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

편집기로 이동