계수 정렬 (counting sort) 을 간단하게 알아보자.

계수 정렬을 간단하게 설명하면?

숫자들 간 비교를 하지 않고 크기를 기준으로 정렬!

 

1. 모든 데이터의 크기 범위를 메모리 상에 표현할 수 있어야 하며 입력 데이터가 큰 경우 매우 비효율적입니다.
2. 범위 조건이 있는 경우에 한해서 매우 빠릅니다.
3. 배열 인덱스의 크기를 기준으로 정렬합니다.

 

 

구현 과정

public class Main {

	public static void main(String[] args) {
		int[] arr = {1,3,2,4,1,23,12,12,3,12,3,23,23};
		int[] cnt = new int[30];        //최대값의 범위를 30으로.
		
		for(int i=0; i<30; i++)       //배열 초기화 
			cnt[i]=0;
		
		for(int i=0; i<arr.length; i++) {    
			cnt[arr[i]-1]++;         //arr배열의 값과 동일한 cnt배열 번호에 삽입. 해당 번호의 배열의 값 증가.
		}                       //-1 해준 이유: 인덱스는 0부터 시작하기 때문. ex)arr[i]=30일 때, cnt[30] <- Error
		
		for(int i=0; i<30; i++) {                 //cnt배열을 1~30까지 탐색 
			for(int j=0; j<cnt[i]; j++) {               
				System.out.print(i+1+" ");          //배열의 값만큼 반복해서 출력. //다시 +1.
			}
		}

	}
}

 

 

시간 복잡도 

• Worst : O(n)
• Average : O(n)
• Best : O(n)