[자바] 계수정렬(Counting sort) 개념과 구현

계수정렬
Counting sort

 

 

계수정렬

별도의 메모리공간을 만들어서 각 원소값 만큼의 index에 해당 원소의 갯수를 채운 뒤 기존 배열의 값을 재설정하는 방식이다.

예를들어, 특정 값이 10만이라고 하면 해당 원소는 index 100,000에 채워지므로 메모리공간의 최대 길이는 10만까지 늘어나서 비효율적이다.

하지만 최대값의 크기가 적당하다면 효율적으로 사용할 수 있겠다.

시간복잡도는 O(n + k)이다. 여기서 k는 위에서 말한 최대 원소값을 뜻한다.

하지만 메모리공간을 HashMap으로 할당함으로써 워스트케이스에 어느정도 대처할 수 있다.

 

 

정렬방식

 

 

이와같이 별도의 메모리공간을 만들고, 각 원소 크기에 해당하는 index를 찾아 해당 원소 갯수만큼 채워넣는다.

모든 값을 채워넣었다면 최종적으로 기존 배열값을 재설정해준다.

 

 

코드구현

메모리공간을 배열로 생성

import java.util.*;

public class 계수정렬 {
    public static void countingSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt(); // 메모리공간의 크기를 경정할 배열 내에 최댓값을 찾는다.
        
        int[] cnt = new int[max + 1]; // 각 원소의 갯수만큼 해당 원소값에 해당하는 index에서 cnt를 늘려간다.

        for (int i = 0; i < arr.length; i++) {
            cnt[arr[i]]++;
        }

        int idx = 0;
        for (int i = 0; i < cnt.length; i++) {
            while (cnt[i] > 0) {
                arr[idx++] = i;
                cnt[i]--;
            }
        }
    }
    
    
    public static void main(String[] args) {     
        int[] arr = {10, 32, 10, 27, 32, 17, 99, 56}; // 출력: [10, 10, 17, 27, 32, 32, 56, 99]
        countingSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

 

위 방법은 메모리공간으로 배열을 만들었다.

단점으로는 최댓값에 따라 시간복잡도가 커져서 비효율적이 될 수 있다.

이번에는 HashMap을 메모리공간으로 할당하여 이 단점을 어느정도 커버해보겠다.

 

메모리공간을 HashMap으로 생성

import java.util.*;

public class 계수정렬 {
    public static void countingSort(int[] arr) {

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int item: arr) {
            map.put(item, map.getOrDefault(item, 0) + 1);
        }

        int idx2 = 0;
        ArrayList<Integer> list = new ArrayList<>(map.keySet());
        Collections.sort(list);

        for (int i = 0; i < list.size(); i++) {
            while (map.get(list.get(i)) > 0) {
                arr[idx2++] = list.get(i);
                map.put(list.get(i), map.get(list.get(i)) - 1);
            }
        }
    }


    public static void main(String[] args) {        
        int[] arr = {10, 32, 10, 27, 32, 17, 99, 56}; // 출력: [10, 10, 17, 27, 32, 32, 56, 99]
        countingSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

HashMap에 데이터를 채워넣으면, 최댓값만큼 메모리공간을 늘리지 않아도 된다.

최댓값의 크기에 따라 배열, HashMap 중 선택해서 사용하는 것을 권장드린다.

 

 

지금까지 계수정렬의 개념과 구현을 알아보았다.