계수 정렬이란

---

• 특정한 조건이 부합할 때만 사용 할 수 있지만 (퀵정렬보다) 매우 빠르게 동작
  - 데이터의 크기 범위가 제한되어 정수 형태로 표현 할 수 있을 때 사용가능
• 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K)를 보장

동작 원리

✅가장 작은데이터 0, 가장 큰 데이터 9

예제

import java.util.*;

public class Main {

    // 데이터(양수) 중 최댓값
    public static final int MAX_VALUE = 9;

    public static void main(String[] args) {

        int n = 15;
        // 모든 원소의 값이 0보다 크거나 같다고 가정
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
        // 모든 범위를 포함하는 크기로 배열 선언(모든 값은 0으로 초기화)
        int[] cnt = new int[MAX_VALUE + 1];

        // 시간 복잡도 : 데이터 개수 N만큼 루프
        for (int i = 0; i < n; i++) {
            cnt[arr[i]] += 1; // 각 데이터에 해당하는 인덱스의 값 증가
        }

        // 시간 복잡도 : 최댓값 K만큼 루프
        for (int i = 0; i <= MAX_VALUE; i++) { // 배열에 기록된 정렬 정보 확인
            // 시간 복잡도 : 전체 수행횟수 N
            for (int j = 0; j < cnt[i]; j++) {
                System.out.print(i + " "); // 띄어쓰기를 기준으로 등장한 횟수만큼 인덱스 출력
            }
        }
    }
}

복잡도

• 계수 정렬의 시간복잡도와 공간 복잡도는 모두 O(N+K)
  - 시간복잡도 : N + K + N => 2N + K => O(N+K)
  - 공간복잡도 : arr의 크기 N + cnt의 크기 K => O(N+K)
• 계수 정렬은 때에 따라서 심각한 (공간복잡도 관련) 비효율성 초래
  ex. 데이터가 0과 999,999(=K)로 단 2개만 존재하는 경우
  -> 총 백만개 크기의 cnt 배열을 만들어야함
  -> 데이터 최댓값 K가 너무 크다면 계수 정렬 사용 어렵다.
• 계수 정렬은 동일한 값을 가지는 데이터가 여러개 등장 할 때 효과적 사용
  ex. 성적의 경우 0점 ~ 100점 까지 범위제한 + 동점 학생이 여러명 일 수 있음