계수 정렬

계수 정렬

데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을대 사용 가능하고, 이 경우에 매우 빠르게 동작한다.

 

 

동작 예시

0) 데이터

- List 객체

https://freedeveloper.tistory.com/274?category=888096

 

1) 원소를 모두 순회하여, List 객체의 인덱스에 해당 숫자가 나오면 +1을 해준다.

- 원소 '7'

https://freedeveloper.tistory.com/274?category=888096

 

- 원소 '5'

https://freedeveloper.tistory.com/274?category=888096

 

2) 모든 원소를 순회한 결과

https://freedeveloper.tistory.com/274?category=888096

 

3) 리스트의 원소를 순회하며 개수만큼 출력한다.

https://freedeveloper.tistory.com/274?category=888096

 

 

 

 

예제코드

public class M12_계수정렬 {

    public static final int MAX_VALUE = 9;

    public static void main(String[] args) {
        int n = 15;

        // 모든 원소의 값이 0보다 크거나 같다고 가정
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};

        // 모든 범위를 포함하는 배열 선언(모든 값은 0으로 초기화)
        int[] cnt = new int[MAX_VALUE + 1];

        for (int i = 0; i < n; i++) {
            cnt[arr[i]] += 1; // 각 데이터에 해당하는 인덱스의 값 증가
        }

        for (int i = 0; i <= MAX_VALUE; i++) { // 배열에 기록된 정렬 정보 확인
            for (int j = 0; j < cnt[i]; j++) {
                System.out.println(i + " "); // 띄어쓰기를 기준으로 등장한 횟수만큼 인덱스 출력
            }
        }
    }
}