[정렬]04. 카운팅 정렬

Counting Sort(계수 정렬)

 

1. 기본 컨셉

요소를 인덱스로 하는 배열에 요소들의 등장 회수를 세어서 저장한 후 정렬에 사용한다.

 

2. 정렬 과정

  다음의 배열 요소를 정렬해보자.

  int [] src = {3,5,7,10,3,10}}

1. 요소의 등장회수를 저장할 배열 생성: 여기서는 10이 가장 크기 때문에 배열의 크기가 11인 count 배열이 필요하다.
   

   

2. count에 각 배열 요소의 등장 회수를 저장한다.
   

   

3. 다음으로 요소들의 위치를 잡기 위해 data 를 누적해준다.
   

   

4. 이제 뒤에서 부터 등장회수 즉 data가 0보다 큰 경우 index에 해당하는 요소들을 누적 데이터에 의해 배치해준다.
   단 인덱스를 표현해야 하므로 -1 해주는 것을 잊지 말자. 또한 배치 이후 data와 누적 data를 모두 -1 처리 해주어야 한다.

   

3. 자바 코드

@Test
public void countSortTest() {
	// 1-1. 최대 값을 찾는다.
	int maxValue = Integer.MIN_VALUE;
	for (int i = 0; i < data.length; i++) {
		if (maxValue < data[i]) {
			maxValue = data[i];
		}
	}
	// 1-2. 최대값  + 1만큼의 크기를 갖는 배열 생성
	int[] counts = new int[maxValue + 1];
	
	// 2. counts에 각 항목별 개수 저장
	for (int i = 0; i < data.length; i++) {
		counts[data[i]]++;
	}
	
	// 3. 아래 부터 누적해서 counts 배열 업데이트 하기
	for (int i = 1; i < counts.length; i++) {
		counts[i] += counts[i - 1];
	}
	
	// 4. 새로운 배열에 정렬해서 저장
	int[] sorted = new int[data.length];
	for (int i = data.length - 1; i >= 0; i--) {
		int loc = counts[data[i]]--;
		sorted[loc - 1] = data[i];
		}
	// 출력
	System.out.printf("counting sort: %s%n", Arrays.toString(sorted));
}

4. 정리

카운트 정렬의 시간 복잡도는 O(n+k)로 나타낼 수 있다. 여기서 n은 데이터의 개수, k는 값의 범위이다.

따라서 조건이 맞기만 하다면 가장 빠른 정렬방식이지만..

요소를 값으로 하는 배열을 써야한다는 점은 가장 큰 단점이다.

만약 {1, 1억}을 정렬한다고 해보자. 겨우 2개의 데이터를 정렬할 예정이지만 count 배열의 크기는  무려 1억1개가 된다.

그만큼 쓸데없는 메모리를 사용한다는 이야기이다.

따라서 카운트 정렬은 좁은 범위 내에서 수가 모여있는 경우 유리하다.

 

또한 카운트 정렬은 요소의 값을 index로 사용하는데 그럴려면 요소들의 값이 index로 표현하기 쉬운 정수형(int, char 등)이어야 한다.