계수 정렬

계수 정렬

계수 정렬은 데이터의 범위가 1000000 이하일 때 효율적으로 사용할 수 있는 알고리즘으로, 시간 복잡도는 O(데이터의 개수 + 데이터의 최대값)입니다.

계수 정렬의 로직은 다음과 같습니다.

1. 정렬된 인덱스의 배열을 만들고 0으로 초기화한다.
2. 데이터가 들어올 때, 데이터와 같은 인덱스를 가지는 배열의 값을 1 증가시킨다. (해당하는 수가 하나 더 있다)
3. 데이터의 삽입이 끝나면, 배열의 인덱스가 가지고 있는 숫자만큼 해당 인덱스를 출력한다.

예를 들면 다음과 같습니다.

데이터가 7 5 1 2 8 2 0 1 8 4 가 있을 때, 배열은 0~8까지의 범위를 가집니다.

0	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0

2번 로직에 따라, 배열을 수정합니다.

0	1	2	3	4	5	6	7	8
1	2	2	0	1	1	0	1	2

각 인덱스를 배열에서 해당 인덱스가 가지는 수만큼 출력하면 다음과 같습니다.

0 1 1 2 2 4 5 7 8 8

정렬이 된 것을 확인할 수 있습니다.

계수 정렬의 문제점

계수 정렬은 인덱스로 정렬된 배열로 정렬하기 때문에, 수의 범위에 따라 공간복잡도가 매우 심해질 수 있습니다. 만약 최솟값이 0이고, 최댓값이 1억이라면, 4억바이트만큼의 공간을 차지합니다. 또한, 예를 들어 데이터의 개수가 2개이지만 그 값이 0과 999999라면, 공간복잡도는 1000000, 즉 범위만큼 배열을 생성해야하기 때문에 비효율성 문제가 심해질 수 있습니다.