[알고리즘] JAVA 계수 정렬 (Counting Sort) 알고리즘

  

 

- '범위 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘

- 계수 정렬의 시간 복잡도는 O(N)

- 기존의 정렬 알고리즘은 위치를 바꾸는 것이고, 이번 계수 정렬은 '크기를 기준'으로 개수만 세우면 되기 때문에 위치를 변경할 필요가 없다.

- 모든 데이터에 한 번씩 접근하면 되기 때문에 매우 효율적

 

문제 

- 1, 3, 2, 4, 3, 2, 5, 3, 1 , 2, 3, 4, 4, 3, 5, 1, 2, 3, 5 ,2, 3, 1, 4, 3, 5, 1, 2, 1, 1, 1을 오름차순으로 나타내시오.

 

소스 코드

package com.company;

public class Main<i> {

    public static void main(String[] args) {
        int[] count = new int[6];
        int array[] = {1, 3, 2, 4, 3, 2, 5, 3, 1 , 2,
                        3, 4, 4, 3, 5, 1, 2, 3, 5 ,2,
                        3, 1, 4, 3, 5, 1, 2, 1, 1, 1};

        for(int i=1; i<=5; i++) {
            count[i] = 0;
        }
        for(int i=0; i<30; i++) {
            count[array[i]]++;
        }
        for(int i=1; i<=5; i++) {
            if(count[i] != 0) {
                for(int j=0; j<count[i]; j++) {
                    System.out.print(i + " ");
                }
            }
        }

    }

}

 

출력 결과