계산 정렬은 특정 범위 내에서 정수를 분류하는 데 사용되는 효율적인 정렬 알고리즘입니다. 각 값의 발생 수를 계산하여 작동하며 정렬 된 배열의 각 요소의 위치를 계산합니다. 이 방법은 입력 데이터의 범위가 분류하는 요소보다 크게 더 크지 않을 때 특히 유용합니다.

분류 작업

알고리즘은 입력 데이터의 각 값의 빈도를 저장하는 카운트 배열을 생성하여 시작합니다. 그런 다음 각 요소의 실제 위치를 정렬 출력에 포함하기 위해이 카운트 배열을 수정합니다. 마지막으로, 계산 배열을 기반으로 정확한 위치에 요소를 배치하여 정렬 된 배열을 구축합니다.

계산 예

우리는 배열이 있습니다 : [4, 2, 2, 8, 3, 3, 1]. 값의 범위는 1에서 8입니다. 계산 프로세스 결과는 다음과 같습니다.

[0, 1, 2, 2, 1, 0, 0, 1]

이 각 숫자의 빈도를 나타냅니다. 알고리즘은 다음 위치를 결정하기 위해 누적 계산을 계산합니다.

[0, 1, 3, 5, 6, 6, 6, 7]

이 작업을 사용하여 정렬 된 배열이됩니다. [1, 2, 2, 3, 3, 4, 8].

응용 프로그램 Scenarios

Counting Sort은 입력 데이터가 알려진, 제한된 범위 내에서 정수로 구성되는 시나리오에 적합합니다. 종종 다음과 같이 사용됩니다.

  • 분류 학생 등급 (예 : 0-100)
  • 주파수 분석에 대한 데이터 구성
  • 임베디드 시스템에서 작은 정수 정렬
  • Radx를 subroutine로 구현

이 효율성은 요소의 수와 상대적 범위의 크기에 따라 달라집니다. 범위가 작을 때, 계산 정렬은 Quicksort 또는 mergesort와 같은 비교 기반 알고리즘을 초과할 수 있습니다.