계수 정렬(counting sort)

개념

- 각 데이터의 갯수를 세어 정렬하는 알고리즘

- 위치를 변경할 필요없고 각 데이터에 한 번씩만 접근하기 떄문에 효율적

- 데이터의 크기 범위가 한정되어 있는 경우에만 사용할 수 있다.

	static final int NUMBER = 5;
	static int[] count = new int[NUMBER];
	static int[] array = {	
    				1, 2, 3, 2, 1, 3 ,5, 4, 3, 5,
				2, 3, 5, 4, 2, 3, 1, 2, 3, 2,
				1, 1, 2, 3, 4, 1, 5, 5, 4, 3
			};
	
	static void countingSort(int[] arr) {
		//배열 초기화
		for (int i = 0; i < count.length; i++) {
			count[i] = 0;
		}
		//각 숫자별 갯수 설정
		for (int i = 0; i < arr.length; i++) {
			count[array[i]-1]++;
		}
		
		for (int i = 0; i < count.length; i++) {
			if(count[i] != 0) {
				for (int j = 0; j < count[i]; j++) {
					System.out.printf(i+1+" ");
				}
			}
		}
		
	}

 

※ 시간복잡도 O(N)