# 계수 정렬 ## 목차 --- 1. 무엇? 2. 특징? 3. 알고리즘 ## 1. 무엇? --- 카운팅을 통한 정렬 기법. 1. 모든 요소 갯수 카운팅 2. 카운팅 정보를 통해 정렬 ## 2. 특징? --- - 빠름, 시간 복잡도 O(n) - 추가 메모리 필요 - 컴팩트 한 값의 범위가 아닌 경우 => 메모리 낭비 ## 3. 알고리즘 --- http://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html ### 소스코드 ``` import java.util.Arrays; import java.util.Collections; public class CountingSort { public static void main(String[] args) { Integer[] a = {1, 0, 3, 1, 3, 1}; a = sort(a); System.out.println(Arrays.toString(a)); } public static Integer[] sort(Integer[] a) { int max = Collections.max(Arrays.asList(a)); Integer[] aux = new Integer[a.length]; Integer[] c = new Integer[max+1]; Arrays.fill(c, 0); // 각 원소 갯수 계산 for (int i=0; i<a.length; i++) { c[a[i]] += 1; } // 누적합 계산 for (int i=1; i<c.length; i++) { c[i] += c[i-1]; } // 누적합을 이용해 정렬 for (int i=a.length-1; i>=0; i--) { aux[--c[a[i]]] = a[i]; } return aux; } } ``` ## Ref. --- 1. 카운팅 소트 - https://bowbowbow.tistory.com/8 2. 시뮬레이션 - http://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html 3. 계수정렬 코드 - https://yaboong.github.io/algorithms/2018/03/20/counting-sort/