[정렬 알고리즘] 계수 정렬 (counting sort)

이민선(Jasmine)·2024년 8월 3일

최근에 싸피에서 반 1등을 하게 되었다. 과목 평가 1등, 월말 평가 2등! 이번에는 아무리 돌이켜봐도 운이 상당히 많이 작용해서 내 실력에 비해 우수한 성적을 낼 수 있었던 것 같다. 초딩 때부터 꼭 이럴 때 자만해서 넘어졌었다. 계속 열심히 공부해야지.

이번주부터 여러가지 정렬 알고리즘을 학습하기 시작했다. 대략적으로 알고리즘 개념만 알고 있고 코드로 구현해본 적은 없었어서, 이번에 스스로 코드를 짜서 구현해보았다. 이번 포스팅에서는 처음 코드로 구현할 때 개인적으로 가장 어려웠던 계수 정렬에 대해 다루려고 한다.

글로 읽는 concept

각 원소의 빈도수를 구하여, 작은 수부터 빈도수만큼 차례대로 나타나게 하여 정렬하는 알고리즘이다.

예를 들어 {3, 5, 2, 5, 3, 3, 1} 이라는 배열이 있다고 가정해보자.
1은 1번, 2는 1번, 3은 3번, 5는 2번 나타난다.
새로운 빈 배열에 해당 빈도수대로 차례대로 추가해주면 {1, 2, 3, 3, 3, 5, 5}와 같이 오름차순 정렬된다.
하지만 정말 말 그대로, 빈도수대로 차례대로 빈 배열에 추가해주는 코드를 직관적으로 떠올려본다면 아마도 이중 for문을 사용해야 할 것이다. 이 때 시간복잡도는 O(중복을 제거한 숫자 개수 * 각 원소의 빈도수) -> O(N^2)으로 간주할 수 있겠다.

대신 빈도수 배열을 누적합 배열로 변경하면, 하나의 for문만 돌더라도 정렬이 가능하다.

각 원소가 새로운 빈 배열에서 어느 인덱스에 위치해야하는지 = 누적합 - 1

이 된다. 원소를 하나 빈 배열에 위치시킨 다음 빈도수를 1만큼 줄이면, for문 순회 시 다음에 같은 숫자가 나왔을 때 위치할 인덱스를 같은 방법으로 계산할 수 있게 된다. 처음에는 이 설명이 이해가 가지 않을 수도 있다. 아래 그림을 보고 이해해보자.

그림으로 보는 concept

위에서 예시로 든 {3, 5, 2, 5, 3, 3, 1}을 계수 정렬할 것이다.
누적합을 구한 결과 아래와 같은 배열이 나왔다.

이제 기존 배열을 하나씩 역방향 순회하면서 (굳이 역방향 순회하는 이유는 아래에서 설명할 것이다.) 빈 배열에 위치시켜나갈 것이다.

1의 경우 누적합이 1이므로 0으로 1만큼 감소시킨 다음 인덱스 0에 위치시킨다.

3의 경우 누적합이 5이므로 4로 1만큼 감소시킨 다음 인덱스 4에 위치시킨다.

그 다음 3의 경우 누적합이 4이므로 (앞서 감소시켰으므로) 3으로 1만큼 감소시킨 다음 인덱스 3에 위치시킨다.

같은 방법으로 모든 숫자를 위치시키고 나면 아래와 같은 모습이 된다.

나의 코드 (오름차순 정렬)

처음에 힘겨웠지만 나름대로 짜낸 코드는 아래와 같다.

public class SortPractice {
	public static void main(String[] args) {
		int[] nums = {6, 50, 24, 12, 50, 50, 24, 0};
		countingSort(nums);
	}

	// counting sort
	public static void countingSort(int[] nums) {
	    // before counting sort : [6, 50, 24, 12, 50, 50, 24, 0]
		System.out.println("before counting sort : " + Arrays.toString(nums));
		
		int max = Integer.MIN_VALUE;
		
		// 최대값 구하기
		for (int num: nums) {
			if (num > max) max = num;
		}
		
		// 빈도수 세기
		int[] freq = new int[max + 1];
		for (int num: nums) {
			freq[num]++;
		}
		
		// 누적합으로 변경
		for (int i=1; i<=max; i++) {
			freq[i] += freq[i - 1];
		}
		
		// 역방향으로 기존 nums를 순회. nums[i]의 누적합 - 1은 sortedNums에서 해당 값이 채워질 index를 의미.
		int[] sortedNums = new int[nums.length];
		for (int i = nums.length - 1;i >= 0;i--) {
			// 인덱스가 되어야 하므로 선위 증감 연산자 사용하여 1만큼 줄인 다음 nums[i]를 할당. 
			sortedNums[--freq[nums[i]]] = nums[i];
		}
		
        // after counting sort : [0, 6, 12, 24, 24, 50, 50, 50]
		System.out.println("after counting sort : " + Arrays.toString(sortedNums));
	}
}

계수 정렬의 특징

시간 복잡도가 원소의 최대값에도 비례한다.

정렬해야 할 원소의 총 개수를 N, 원소의 최대값을 M이라고 할 때 시간복잡도는 O(N + M)이다. 시간복잡도 O(N^2)인 버블 정렬이나 선택 정렬과 비교하면 빅오 표기만 놓고 보았을 때는 훨씬 효율적이다.

역방향 순회가 왜 필요한가요? 안정 정렬.

계수 정렬은 안정 정렬(stable sort)이라고 할 수 있다. 동일한 값을 가진 원소에 대해 정렬이 된 이후에도 순서가 유지된다는 점이다.
이를 위해서는 알고리즘에서 역방향 순회가 이루어져야 한다. 동일한 숫자가 위치할 인덱스는 점점 줄어드므로, 숫자도 뒤에서부터 위치해야 순서가 유지되기 때문이다.