계수정렬 (Counting Sort) 이란? 굉장히 빠른 속도를 자랑하는 정렬 (Sort) 이다. 배열에 들어있는 원소의 최대값을 k 라고 가정하면 O(k + n) 의 시간복잡도로 정렬할 수 있다. 그러므로 최선의 경우에서는 퀵정렬보다도 빠르다. 하지만 k 값이 클 경우, 예를 들어서 배열 내의 원소의 최대값이 매우 큰 숫자일 경우 비효율적인 알고리즘이다. 그러므로 배열 내의 원소의 값이 간단한 경우 (예, 1~2자리의 숫자) 에 효율적인 알고리즘이다. 실행 과정 계수정렬은 배열 내에 속해있는 모든 원소를 인덱스로 가지는 배열을 생성한다. 그리고, 각각의 인덱스에 배열 내의 원소가 몇번 들어가는지 계산한다. 아래와 같은 정렬하기 원하는 배열이 있다고 가정하자. 배열 내의 각 원소가 몇번 나오는지 계산하기..