도수 정렬

도수정렬은 요소의 대소관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘이다.

데이터를 비교,교환하는 작업이 필요 없어 매우 빠르다.

하지만 도수분포표가 필요하기 때문에 데이터의 최솟값과 최댓값을 미리 알고있을 경우에만 사용할 수 있다.

 

public class CountingSort {

    public static void main(String[] args) {
        System.out.println("도수정렬");
        System.out.println("요솟수: 7 ");
        int nx = 7;
        int[] x = new int[]{22,5,11,32,120,68,70};
        
        int max = x[0];
        for (int i = 1; i < nx; i++) {
            if(x[i] > max) max = x[i];
        }

        countingSort(x, nx, max);

        System.out.println("오름차순으로 정렬했습니다");
        for (int i = 0; i < nx; i++) {
            System.out.println("x["+i+"]= "+x[i]);
        }

    }
    // 도수 정렬(0이상 max 이하의 값을 입력)
    static void countingSort(int[] a, int n, int max) {
        int[] f = new int[max+1]; // 누적도수
        int[] b = new int[n]; // 작업용 목표 배열
        
        for(int i = 0; i < n; i++) f[a[i]]++; // 도수분포표 만들기
        for(int i = 1; i <= max; i++) f[i] += f[i-1]; //누적도수분포표 만들기
        for(int i = n-1; i>=0; i--) b[--f[a[i]]] = a[i];  // 목표배열 만들기(앞에서부터하면 안정적이지 않음)
        for(int i = 0; i < n; i++) a[i] = b[i]; // 배열 복사하기
        
    }
}