센 값
이동
카운터

  • 세는 중
  • 방금 이동
  • 제자리

계수 정렬 자세히 알아보기

계수 정렬

계수 정렬은 값이 좁은 범위의 정수일 때 쓸 수 있습니다. 나올 수 있는 값마다 카운터를 하나씩 두고 각 값이 몇 번 나오는지 센 뒤, 그 개수로 모든 값이 들어갈 자리를 정확히 알아냅니다. 목록을 읽는 동안 카운터가 채워지고, 각 값이 자기 구간으로 옮겨 갈 때마다 다시 줄어드는 모습을 한 단계씩 지켜보세요. ‘재생’을 눌러 정렬을 보거나, ‘단계’와 ‘뒤로’로 이동을 하나씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 목록과 버퍼 행 사이의 띠에는 값마다 카운터가 하나씩 있습니다. 타일에는 센 값, 이동, 카운터 수가 표시됩니다. 막대 개수와 시작 순서를 고르거나 직접 숫자를 입력하세요. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.

작동 원리

  1. 막대 개수와 시작 순서를 고르거나 직접 정수를 입력하세요. 값 종류가 적은 목록도 해 보세요.
  2. ‘재생’을 누르거나, ‘단계’와 ‘뒤로’로 값을 하나씩 옮기세요. 단계 슬라이더를 끌면 정렬의 원하는 지점으로 이동합니다.
  3. 카운터를 보세요: 목록을 읽는 동안 채워지고, 각 값이 놓일 때마다 하나씩 줄어듭니다.

계수 정렬의 원리

가장 작은 값부터 가장 큰 값까지 모든 값마다 카운터를 만듭니다. 목록을 한 번 읽으며, 보이는 값의 카운터에 1을 더합니다. 그런 다음 가장 작은 값부터 개수를 차례로 더합니다: 어떤 값의 구간은 더 작은 값들이 모두 끝난 바로 다음에서 시작합니다. 마지막으로 목록을 다시 훑으며 모든 값을 자기 구간의 다음 빈자리로 옮기고, 결과를 다시 복사합니다.

범위가 좁으면 빠르다

계수 정렬은 목록을 두 번 읽고 카운터를 한 번 훑으므로, 작업량은 n + k, 즉 값의 개수와 카운터 개수의 합에 비례합니다. 0부터 100까지의 시험 점수나 나이처럼 좁은 범위에 값이 많으면 어떤 비교 정렬보다도 빠릅니다. 범위가 넓으면 아무도 쓰지 않는 카운터에 시간과 메모리를 낭비합니다: 1부터 1,000,000까지 흩어진 값 세 개에 카운터 백만 개가 필요합니다. 기수 정렬이 자릿수마다 반복하는 단계이기도 합니다.

자주 묻는 질문

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

각 값이 몇 번 나오는지 세고, 개수를 차례로 더해 각 값의 구간이 어디서 시작하는지 찾은 뒤, 모든 값을 곧바로 자기 구간의 다음 빈자리로 옮깁니다. 두 값을 비교하는 일은 없습니다.

계수 정렬은 언제 써야 하나요?

값이 정수이거나 정수로 바꿀 수 있고, 최솟값부터 최댓값까지의 범위가 값의 개수보다 크게 넓지 않을 때입니다: 성적, 나이, 작은 코드 등. 이때 걸리는 시간은 n + k에 비례합니다.

계수 정렬은 안정 정렬인가요?

네, 여기서처럼 값을 목록 순서대로 자기 구간의 다음 빈자리로 옮기면 안정적입니다. 그래서 기수 정렬이 자릿수마다 계수 정렬을 쓸 수 있습니다.

센 횟수만큼 각 값을 그냥 쓰면 안 되나요?

단순한 숫자라면 그래도 되고, 오히려 더 간단합니다. 하지만 실제 데이터에는 점수마다 이름이 붙어 있듯이 키 말고도 다른 정보가 있는 경우가 많아서, 센 키만 쓰면 그 정보를 잃습니다. 항목 자체를 옮기면 딸린 정보가 모두 그대로 남습니다.

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

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

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

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

편집기로 이동