[알고리즘] 정렬(4) - 계수 정렬(Counting Sort)

원리 1. 집합의 최댓값을 구해서 최대값만큼의 메모리를 차지하는 카운팅 배열을 만든다. 2. 각원소의 개수를 카운팅시킨다 3. 카운팅 배열의 누적합을 구한다. 4. 카운팅 배열을 통해 순서대로 수를 나열한다. [ 15, 13, 10, 7, 5, 5, 1, 0, 7 ] 카운팅 배열에는 다음과 같이 구성될 수 있습니다. Index 0 1 5 7 10 13 15 count 1 1 2 2 1 1 1 다음을 누적합의 표입니다. Index 0 1 5 7 10 13 15 count 1 2 4 6 7 8 9 이때, 누적합을 구하는 이유는 어느 인덱스에 원본 원소가 들어갈지 순서를 강제하기 위해서 입니다. 정렬된 원소들이 들어갈 배열의 인덱스를 카운팅배열의 데이터 - 1로 설정 해줌으로서 정렬 해줄 수 있습니다. 예를들..

2020.04.08