계수 정렬(Counting Sort) 알고리즘 구현하기

이번에는 자바로 계수정렬 알고리즘을 직접 구현해보겠습니다
이전에 사용했던 [4, 2, 2, 8, 3, 3, 1] 배열을 오름차순 정렬할 것입니다

계수 정렬 알고리즘 구현 - Java

public class Main {  
  
    public static void main(String[] args){  
        int[] arr = {4, 2, 2, 8, 3, 3, 1};  
        System.out.print(Arrays.toString(countingSort(arr)));  
    }  
  
    private static int[] countingSort(int[] arr) {  
        if(arr.length == 0){  
            return arr;  
        }  
  
        int max = Arrays.stream(arr).max().getAsInt();  
  
        int[] count = new int[max+1];  
        for (int i = 0; i < arr.length; i++) {  
            count[arr[i]]++;  
        }  
  
        for (int i = 1; i < count.length; i++) {  
            count[i] += count[i-1];  
        }  
  
        int[] sorted = new int[arr.length];  
  
        for (int i = arr.length-1; i >= 0; i--) {  
            sorted[count[arr[i]] - 1] = arr[i];  
            count[arr[i]]--;  
        }  
        return sorted;  
    }  
}

위와같이 구현했습니다
구현 프로세스는 이전에 정리한 동작 방식과 동일합니다

계수배열을 반들어 개수를 세어주고, 누적합을 적용합니다
이후, 정렬된 결과를 받을 배열을 만들고 안정정렬을 보장하기 위해 역순 탐색을 합니다
개수-1 위치에 원소를 배치하고, 그 원소의 개수를 감소시킵니다

결과 확인

결과 : [1, 2, 2, 3, 3, 4, 8]

위와같이 오름차순 정렬된 결과를 확인할 수 있습니다