계수 정렬 (Count Sort)

1. 개요

• 계수 정렬은 비교를 사용하지 않는 정렬 알고리즘이다.
• 정렬해야 할 요소들의 값 범위가 제한적일 때 효과적이다.
• 정렬하려는 입력 배열에서 각 요소의 발생 횟수를 세고, 이 정보를 바탕으로 각 요소가 정렬된 배열에서 어디에 위치해야 하는지를 결정한다.
• 작은 정수를 정렬할 때 높은 성능을 보이며, 복잡한 비교 연산 없이 빠르게 정렬을 수행할 수 있다.

---

2. 특징

• 시간복잡도: O(n+k)
• n은 배열의 크기, k는 입력 데이터의 최대값
• 공간 복잡도: O(k)
• 각 입력 데이터의 발생 횟수를 저장하기 위한 배열 필요

---

3. 코드

import java.util.Arrays;

public class CountingSortTest {

	public static void main(String[] args) {
		int[] arr = { 4, 2, 2, 8, 3, 3, 1 };

		countSort(arr);

		System.out.println(Arrays.toString(arr));
	}

	private static void countSort(int[] arr) {
		int n = arr.length;

		// 배열 arr에서 최대값 찾기
		int max = arr[0];
		for (int i = 1; i < n; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
		}

		// 각 숫자의 발생 횟수를 저장할 배열(counts) 생성
		int[] counts = new int[max + 1];

		// arr의 각 요소의 발생 횟수를 counts 배열에 저장
		for (int i = 0; i < n; i++) {
			counts[arr[i]]++;
		}

		// counts 배열을 수정하여, 각 요소까지의 누적 발생 횟수를 저장
		for (int i = 1; i <= max; i++) {
			counts[i] += counts[i - 1];
		}

		// 결과를 저장할 배열(output) 생성
		int[] output = new int[n];

		// arr의 요소들을 output 배열에 정렬하여 저장
		for (int i = n - 1; i >= 0; i--) {
			output[counts[arr[i]] - 1] = arr[i];
			counts[arr[i]]--;
		}

		// 정렬된 데이터를 원래의 배열(arr)로 복사
		for (int i = 0; i < n; i++) {
			arr[i] = output[i];
		}
	}

}