계수 정렬
: 입력 데이터의 범위가 제한적일 때, 각 데이터의 출현 빈도를 계산하여 이를 기반으로 정렬하는 비교 기반이 아닌 정수형 데이터 정렬 알고리즘
- 활용
주로 데이터의 범위가 좁고, 값이 정수일 때 효율적으로 사용 - 장점
데이터 간 비교를 수행하지 않아 O(nlogn)의 시간복잡도를 가지는 퀵 정렬, 병합정렬 보다 빠르다, - 단점
많은 메모리 공간 필요,
카운트 배열의 인덱스를 통해 숫자의 갯수를 세기 때문에 음수가 존재하면 사용 불가
구현방법
- 정렬할 숫자들을 배열(arr)에 입력 받기
- 카운트 배열(count) 생성 : 각 숫자의 빈도 수를 센다.
- 배열의 크기 = ( arr의 최댓값 + 1 )
- 누적 수를 저장할 배열(cumCount) 생성 : 각 숫자까지 몇 개의 원소가 나왔는지 센다.
- 카운트 배열을 누적시켜 각 숫자의 위치를 알 수 있게 한다.
- 배열 정렬 :
- arr 배열의 각 원소를 역순으로 순회하면서, cumCount 배열을 기반으로 해당 원소의 인덱스를 설정하고 값을 삽입한다.
시간복잡도
N은 배열의 크기, M은 배열의 최댓값이라 가정할 때 :
- 시간복잡도는 O(N + M)
- 공간복잡도는 O(N + M)
참고
-
계수 정렬 시각화 :
https://www.geeksforgeeks.org/counting-sort-visualization-using-javascript/ -
정렬 알고리즘 시간 복잡도 비교 :
| 알고리즘 | 최악(Worst) | 최선(Best) | 평균(Average) |
|---|---|---|---|
| 버블 정렬(Bubble Sort) | O(n²) | O(n²) | O(n²) |
| 선택 정렬(Selection Sort) | O(n²) | O(n²) | O(n²) |
| 삽입 정렬(Insertion Sort) | O(n²) | O(n) | O(n²) |
| 퀵 정렬(Quick Sort) | O(n²) | O(nlogn) | O(nlogn) |
| 병합 정렬(Merge Sort) | O(nlogn) | O(nlogn) | O(nlogn) |
| 힙 정렬(Heap Sort) | O(nlogn) | O(nlogn) | O(nlogn) |
| 기수 정렬(Radix Sort) | O(n) | O(n) | O(n) |
| 계수 정렬(Counting Sort) | O(n) | O(n) | O(n) |
✿.｡.:* ☆:**:. 🎀 Daily Study 🎀 .:**:.☆*.:｡.✿