계수 정렬(Counting Sort)

"계수 정렬"

     : 크기를 기준으로 세는 알고리즘

 

• 시간 복잡도 : O(N)

 

• '범위 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘
• 크기를 기준으로 개수만 세주면 되기 때문에 위치를 바꿀 필요가 없음
• 모든 데이터에 한 번씩만 접근하기 때문에 효율적

 

class Sort {
	
	public int[] Counting_Sort(int[] arr, num) {
		
		int[] count = new int[num];
		
		
		for(int i = 1; i <= num; i++) // count 배열을 0으로 초기화
			count[i] = 0;
		
		
		for(int i = 0; i < arr.length; i++) // count 배열에 개수를 저장
			count[arr[i]]++;
		
		
		for(int i = 1; i <= num; i++) { // 출력
			
			if(count[i] != 0) {
				
				for(int j = 0; j < count[i]; j++)
					System.out.println("%d", i);
			}
		}
	}
}