계수 정렬 (Counting Sort)

특징

• 숫자끼리 비교하지 않고, 카운트를 세서 정렬하는 방식
• 카운팅을 위한 메모리 필요
• O(n+k)
  • k는 정렬 대상 데이터 중 최대값으로, k가 n보다 더 커서 worst한 케이스를 만들 수

정렬 과정

• 원소 중 가장 큰 값으로 배열 사이즈를 잡아서, 카운팅 테이블을 만든다
• 각 위치의 값을 카운팅 개수만큼 뽑아준다
  

소스코드

// 계수 정렬

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;

public class Main2 {
    public static void countingSort(int[] arr) {
        // # 1 일반 배열 사용
        // 최대값 구해서 배열 설정
        int max = Arrays.stream(arr).max().getAsInt();  //최대값 구함
        int[] cntArr = new int[max + 1];    //카운팅 테이블 생성

        for (int i = 0; i < arr.length; i++) {
            cntArr[arr[i]]++;   //각 값에 대해 해당 카운팅 테이블의 값 수정
        }

        int idx = 0;
        //카운팅 테이블의 값을 뽑아내며 arr 배열에 정렬
        for (int i = 0; i < cntArr.length; i++) {
            while (cntArr[i] > 0) {
                arr[idx++] = i;
                cntArr[i] -= 1;
            }
        }

        // # 2 Hashmap 사용
        // 숫자가 많지 않은데, 수가 너무 크면 메모리 낭비가 될 수 있으므로 HashMap 사용
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int item: arr) {   //arr의 값을 key로 해서 HashMap에 넣는다
            map.put(item, map.getOrDefault(item, 0) + 1);
        }

        int idx2 = 0;
        ArrayList<Integer> list = new ArrayList(map.keySet());  //HashMap의 key들을 값으로 담고있는 리스트 생성
        Collections.sort(list); //리스트를 오름차순 정렬

        for (int i = 0; i < list.size(); i++) {
            int cnt = map.get(list.get(i)); //카운팅 테이블의 값 조회
            while (cnt > 0) {
                arr[idx2++] = list.get(i);
                cnt--;
            }
        }
    }

    public static void main(String[] args) {
        // Test code
        int[] arr = {10, 32, 10, 27, 32, 17, 99, 56};
        countingSort(arr);
        System.out.println("계수 정렬: " + Arrays.toString(arr));
    }
}