계수 정렬 Counting Sort

Intro::

계수 정렬에 대해 알아보자.

정의

계수 정렬(Counting Sort)은 정수나 정수로 표현될 수 있는 값을 정렬할 때 사용하는 비교 기반 정렬 알고리즘이 아닌 정렬 방법입니다. 이 알고리즘은 입력된 원소의 값이 얼마나 자주 등장하는지 세어서, 그 개수에 따라 원소의 위치를 결정합니다. 계수 정렬은 특정 조건 하에서 매우 빠른 정렬 속도를 자랑하는데, 그 조건은 정렬하려는 숫자의 범위가 작을 때입니다.

계수 정렬의 기본 원리

입력 배열에서 최소값과 최대값을 찾습니다.

최소값과 최대값의 범위를 포함하는 길이를 갖는 카운트 배열을 생성합니다.

입력 배열을 순회하며, 각 숫자가 나타난 횟수를 카운트 배열에 기록합니다.

카운트 배열을 순회하며, 각 숫자의 개수만큼 숫자를 출력 배열에 채웁니다.

장점 : O(n) 의 시간복잡도

단점 : 배열 사이즈 N 만큼 돌 때, 증가시켜주는 Counting 배열의 크기가 큼.

코드


package algorithm;

import java.util.Arrays;

public class CountingSort {
	void sort(int[] arr) {
		int n = arr.length;
		// 배열에서 최대값과 최소값 찾기
		int max = arr[0];
		int min = arr[0];
		for (int i = 1; i < n; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
			if (arr[i] < min) {
				min = arr[i];
			}
		}
		// 카운트 배열 초기화
		int range = max - min + 1;
		int[] count = new int[range];
		// 입력 배열의 각 요소 카운팅
		for (int i = 0; i < n; i++) {
			count[arr[i] - min]++;
		}
		// 카운트 배열 변경: 각 값이 최종적으로 위치할 시작 인덱스를 반영
		for (int i = 1; i < range; i++) {
			count[i] += count[i - 1];
		}
		// 결과 배열 생성 및 입력 배열의 요소 배치
		int[] output = new int[n];
		for (int i = n - 1; i >= 0; i--) {
			output[--count[arr[i] - min]] = arr[i];
		}
		// 원래 배열에 정렬된 요소 복사
		System.arraycopy(output, 0, arr, 0, n);
	}

	public static void main(String[] args) {
		CountingSort cs = new CountingSort();
		int[] arr = {4, 2, 2, 8, 3, 3, 1};
		cs.sort(arr);
		for (int i : arr) {
			System.out.print(i + " ");
		}
	}
}

/*
정렬 전 배열:[4, 2, 2, 8, 3, 3, 1]
					 1  2  3  4  5  6  7  8 의 개수를 구해준다.
count 배열:[1, 2, 2, 1, 0, 0, 0, 1]
count 배열:[1, 3, 5, 6, 6, 6, 6, 7]
정렬 후 배열:[1, 2, 2, 3, 3, 4, 8]
*/

계수 정렬 Counting Sort

Intro::

정의

계수 정렬의 기본 원리

코드

References::