ki hyun's 개발블로그

O(n)의 등장 이때까지 봐온 모든 정렬 알고리즘들은 입력된 숫자들을 비교해가며 정렬을 하였다. 하지만 비교하며 정렬하는 모든 알고리즘은 O(n log n)이라는 명확한 한계를 가지고 있다. 그렇다면 어떻게하면 정렬 알고리즘을 더욱 빠르게 작동시킬 수 있을까? 바로 비교를 하지 않으면 된다. O(n) 시간에 실행되는 정렬 알고리즘들은 비교를 하지 않고 정렬을 한다는 특징을 가지고 있다. 계수 정렬 계수 정렬은 말 그대로 x에 대해서 x보다 같거나 작은 원소의 개수를 센다. 이렇게 센 값은 나중에 x를 어디에 배치할 것인가를 결정할 때에 사용된다. 예를 들어 [2, 1, 3, 4, 8, 7, 9] 라는 배열이 있다고 가정해보자 이때 x에 대해서 같거나 작은 원소의 개수를 센다면 0 = 0 1 = 1 2 =..