계수 정렬이란 크기를 기준으로 데이터의 개수를 세는 정렬 알고리즘이다. 각 데이트를 바로 크기를 기준으로 분류하므로 O(N)의 시간 복잡도를 가진다.
이러한 배열로 만들어서 인덱스 차례대로 해당 원소를 1씩 줄여나가면서 출력하게 되면 정렬된 데이터를 확인할 수 있다.
출력 값 : 0 0 1 1 1 2 2 2 3 3
계수정렬을 C언어로 구현한 코드는 여기에서 확인할 수 있다.
계수 정렬은 가장 큰 데이터의 크기만큼 메모리를 할당 해중야 하기 때문에 데이터의 크기가 한정적일 때 사용할 수 있다.
'[알고리즘] 문제 풀이 > 자료구조 | 알고리즘' 카테고리의 다른 글
| 2021.2.25 TIL : [자료구조] 순차 탐색과 이진 탐색(Sequential Search and Binary Search) (0) | 2021.02.26 |
|---|---|
| 2021.2.23 TIL : [자료구조] 이진트리의 개념, 구현 및 순회 (0) | 2021.02.24 |
| 2021.2.21 TIL : [자료구조] 퀵 정렬(Quick Sort) (0) | 2021.02.21 |
| 2021.2.20 TIL : [자료구조] 선택 정렬과 삽입정렬 (0) | 2021.02.20 |
| 2021.2.9 TIL : [자료구조] 스택(Stack) (0) | 2021.02.09 |
댓글