계수

[알고리즘] 계수 정렬 (key-indexed counting sort) / C++ 구현

0. 계수 정렬 소개 계수 정렬은 O(n)의 시간복잡도를 가지고 있는, 매우 빠른 정렬 방식이다. 또한 숫자가 중복되거나 말거나 상관 없이 같은 속도로 정렬이 가능하다. 하지만, 정렬하고자 하는 배열 외에 (1)문자의 개수를 셀 때 사용하는 배열, (2)새롭게 정렬해야 하는 배열, 이렇게 두개의 배열의 메모리가 더 필요하다. 즉, 매우 큰 수를 정렬하고자 할 때, 그 만큼 큰 용량의 메모리가 필요하다. 이렇게 설명하면 알기 쉽지 않다. 기초부터 한번 알아보자. 1. Key와 Radix 계수 정렬을 이해하기 위해서는 Radix라는 개념을 알아야 한다. 다음 표를 보자. Binary(2진수), Decimal(10진수), Upper/Lower case(대소문자), ascii코드 등, 익숙한 문자들이 많이 보일..