(참고 : https://velog.io/@chappi/알고리즘-6일차-On-정렬-계수-정렬)
계수 정렬
O(N^2) 정렬은 내 옆의 수와 비교하는 것이고,
O(NlogN) 은 옆 말고 건너 건너 수와 비교하기에 하나당 logN x N이라고 한다.
따라서 O(N)은 배열 내부의 숫자와 비교를 하지 않는다.
데이터는 양수이면서, 범위가 너무 크지 않아야 한다.
계수 정렬 알고리즘
[2,4,3,3,0,0,5] 이 있다면
미리 이 배열의 길이만큼 빈 배열을 만들어 준다.
[ x,x x,x x,x x ]
그리고 각 요소의 갯수를 구한다.
0의 갯수 2개
2의 갯수 1개
3의 갯수 2개
4의 갯수 1개
5의 갯수 1개
그리고 맨 뒤에서 부터 빈 배열의 끝에 넣어준다.
[0,0,2,3,3,4,5]
더 구체적으로 살펴보자
원래 배열 : [2,4,3,3,0,0,5]
원래 배열의 가장 큰 수인 5까지 인덱스가 있는 (길이 6)이고
각 인덱스에 맞는 배열의 요소(숫자)가 몇 개 있는지 나타내는
count 배열을 만든다.
(인덱스 : [0,1,2,3,4,5])
count : [2,0,1,2,1,1]
이렇게 말이다.
그리고 count 배열의 누적합을 구해 배열을 수정한다.
누적합은 현재 숫자 + 앞의 숫자의 개수로 정해준다.
예를 들어 인덱스 4는 본인을 포함해 2+1+2+1 = 6인 것이다.
인덱스 : [0,1,2,3,4,5]
이전 count : [2,0,1,2,1,1]
이후 count : [2,2,3,5,6,7]
이렇게 누적으로 count 배열을 수정한다.
그리고 다시 본래 배열의 요소마다 count배열을 이용해 result 배열에 넣는다.
array.forEach((val) => {
result[count[val] -1 ] = val;
count[val]--;
});구체적 예시로 보면 원래 배열의 첫 요소인 2는 count[2] - 1 = 2가 되고
result의 2번 인덱스에 2가 들어간다.
[undefined,undefined,2]
그리고 count[2]--로 2가된다.
다음 원래 배열의 요소 4는 count[4] - 1 = 5가되고,
result의 5번인덱스에 4가 들어간다.
[undefined,undefined,2,undefined,4,]
이런식으로 진행하면 배열이 정리가 된다.
