카운팅정렬 시각화
비교 없이 빈도를 세어 정렬하는 과정을 3개 배열로 관찰합니다
정렬★☆☆
속도
1 / 1단계: 최댓값: 20
배열 크기16
입력 배열카운트 배열출력 배열활성
빈도를 세고, 누적합을 구하고, 출력 배열에 배치하는 3단계를 관찰하세요.
카운팅정렬이란?
카운팅정렬(Counting Sort)은 비교 없이 각 값의 출현 빈도를 세어 정렬하는 알고리즘입니다. O(n+k) 시간 복잡도로, 값의 범위(k)가 작을 때 매우 빠르며 안정 정렬입니다.
사용 방법
- 1배열 크기를 조절하세요
- 2중복 많은 버튼으로 같은 값이 많은 입력을 생성하세요
- 33개 배열(입력/카운트/출력)이 동시에 표시됩니다
- 4빈도 세기 → 누적합 → 배치 3단계를 순서대로 관찰하세요
동작 원리
- 1입력 배열의 최댓값(k)을 찾습니다
- 2크기 k+1의 카운트 배열을 생성하고 각 값의 출현 횟수를 기록합니다
- 3카운트 배열을 누적합으로 변환하여 각 값이 출력에서 어디에 위치할지 결정합니다
- 4입력 배열을 역순으로 순회하며 올바른 위치에 배치합니다
- 5시간 O(n+k), 공간 O(n+k)
실무 활용
- •시험 점수 정렬(0~100점 범위) — 값 범위가 제한적일 때 매우 빠릅니다
- •나이/등급/상태코드 등 정수 키 기반 데이터 분류에 사용됩니다
- •래딕스정렬의 내부 서브루틴(각 자릿수별 카운팅)으로 사용됩니다
- •히스토그램 생성 및 빈도 분석에 활용됩니다
- •데이터베이스의 Bitmap Index 구축에 사용됩니다
비슷한 알고리즘
- •버블/퀵/병합 정렬 — 비교 기반으로 최소 O(n log n). 카운팅정렬은 비교 없이 O(n+k)로 더 빠르지만 메모리 O(k) 필요
- •래딕스정렬 — 카운팅정렬을 자릿수별로 반복 적용. 큰 범위의 정수도 처리 가능합니다
- •버킷정렬 — 값을 구간(버킷)별로 분배 후 개별 정렬. 실수값도 처리 가능합니다
학습 팁
- •비교 기반 정렬의 하한 O(n log n)을 우회합니다
- •값의 범위가 크면 메모리 낭비가 심합니다
- •안정 정렬이므로 래딕스 정렬의 서브루틴으로 사용됩니다
- •음수 값은 오프셋을 더해 처리할 수 있습니다
자주 묻는 질문
Q. 언제 사용하나요?
A. 값의 범위(k)가 n과 비슷하거나 작을 때 (예: 시험 점수 0-100, 나이 0-150). k >> n이면 비효율적입니다.
Q. 시간 복잡도는?
A. O(n+k)입니다. n은 배열 크기, k는 값의 범위. 공간도 O(n+k).