카운팅 정렬(Counting Sort)

카운팅 정렬(Counting Sort)

항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘

제한 사항

■ 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능 : 각 항목의 발생 회수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문이다.

■ 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 한다.

시간 복잡도

■ 시간 복잡도 O(n+k) : n은 리스트 길이, k는 정수의 최대값 

import java.util.Arrays;
 
public class CountingSort {
    public static void main(String[] args) {
        int[] arr= {0,4,1,3,1,2,4,1};
        int[] counts = new int[5]; //arr배열의 최댓값+1 만큼 배열의 크기 설정 (원래는 arr 배열에서 최댓값 구해서 counts 배열 크기 설정해줘야됨)
        int[] temp = new int[arr.length]; //정렬 배열
        for (int i = 0; i < arr.length; i++) { //counts[i] = i의 발생 횟수
            counts[arr[i]]++;
        }
        for (int i = 0; i < counts.length-1; i++) {//정렬된 집합에서 각 항목의 앞에 위치할 항목의 개수를 반영하기 위해 counts 원소를 조정
            counts[i+1] += counts[i];
        }        
        
        for (int i =arr.length-1; i >=0; i--) {
            counts[arr[i]]--;
            temp[counts[arr[i]]] = arr[i];
            
        }
        
        System.out.print(Arrays.toString(temp));
    }
}