[자료구조] 계수정렬

계수정렬이란?

계수정렬(Counting sort)은 크기를 기준으로 데이터의 개수를 세는 정렬 알고리즘. 배열의 크기를 인덱스로 삼고, 해당 인덱스에 속하는 데이터의 수를 저장한 뒤, 순서대로 나열함.

 

• 데이터를 바로 크기 기준으로 분류하므로 O(N)의 시간 복잡도를 가짐
• 배열의 크기를 기준으로 배열을 세기 때문에 인덱스를 넘어가는 수는 정렬못함(→ 메모리소모가 큼)

이미지 출처 : https://www.thecrazyprogrammer.com/2015/04/counting-sort-program-in-c.html

 

 

 

 

참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수