TUTORIAL · Algorithm

계수 정렬

이 자습서에서는 계산 정렬 알고리즘을 소개합니다.

작성자 Harshit Jindal게시일 2021-02-09업데이트 2023-10-12
이 페이지의 내용

계수 정렬은 비 비교 정렬 알고리즘입니다. 각 고유 요소의 발생 횟수를 계산하여 배열을 정렬합니다. 고유 한 요소의 개수를 부분적으로 해시 한 다음 계산을 수행하여 정렬 된 최종 배열에서 각 요소의 인덱스를 찾습니다. 상당히 빠른 알고리즘이지만 대규모 데이터 세트에는 적합하지 않습니다. 기수 정렬 내에서 서브 루틴으로 사용됩니다.

계산 정렬 알고리즘

n 요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정 해 보겠습니다.

  • 배열 내에서 최대 요소 max와 최소 요소 min을 찾습니다.
  • 모든 요소가 0으로 설정된 max-min + 1길이의 배열 count를 초기화합니다.
  • 입력 배열 A와 같은 크기의 배열 ‘출력’을 초기화합니다.
  • min을 빼고 그 차이를 인덱스로 사용하여 count배열 안에있는 모든 요소의 개수를 저장합니다.
  • count 배열 내부의 요소 합계를 누적합니다. 이제count 배열은 정렬 된 배열에서 각 요소의 위치를 ​​보유합니다.
  • 끝에서 시작하여A에서 요소를 가져오고 다음을 수행하십시오.
  • 요소 인덱스를count[A[i] -min] -1로 계산하고A[i]를output에 저장합니다.
  • count[A[i] -min]을1만큼 줄입니다.
  • output 요소를 원래 배열A에 다시 저장합니다.

계산 정렬 예

배열이(6, 3, 2, 7, 4, 5, 4, 2)라고 가정합니다. 계산 정렬 알고리즘을 사용하여 정렬합니다.

  • maxm = 7
  • minm = 2
  • 범위= 6
  • count와output은 0으로 초기화됩니다.
인덱스 0 1 2 삼 4 5
값 0 0 0 0 0 0
  • 모든 요소의 개수를 계산 한 후count 배열.
인덱스 0 1 2 삼 4 5
값 2 1 2 1 1 1
  • 요소의 합을 누적 한 후count 배열.
인덱스 0 1 2 삼 4 5
값 2 삼 5 6 7 8
  • 첫 번째 반복 :A[7] = 2
count 1 3 5678
output ‘0 2 0 0 0 0 0 0’
  • 두 번째 반복 :A[6] = 4
count 1 34678
output ‘0 2 0 0 4 0 0 0’
  • 세 번째 반복 :A[5] = 5
count ‘1 34 5 7 8’
output ‘0 2 0 0 4 5 0 0’
  • 네 번째 반복 :A[4] = 4
count ‘1 3 3 5 7 8’
output ‘0 2 0 4 4 5 0 0’
  • 다섯 번째 반복 :A[3] = 7
count 1 3 3 5 7 7
output 0 2 0 4 4 5 0 7
  • 여섯 번째 반복 :A[2] = 2
count 0 3 3 5 7 7
output 2 2 0 4 4 5 0 7
  • 일곱 번째 반복 :A[1] = 3
count 0 2 3 5 7 7
output 2 2 34 5 0 7
  • 여덟 번째 반복 :A[0] = 6
count 0 2 3 5 6 7
output 2 2 34 4 5 6 7

마지막으로 output배열을 A안에 저장하고 정렬 된 배열 인 2, 2, 3, 4, 4, 5, 6, 7을 얻습니다.

계산 정렬 알고리즘 구현

#include <iostream>
using namespace std;
const int N = 10;

int maxm(int arr[], int n) {
  int max = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

int minm(int arr[], int n) {
  int min = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] < min) {
      min = arr[i];
    }
  }
  return min;
}

void countingSort(int arr[], int n) {
  int min = minm(arr, n);
  int max = maxm(arr, n);
  int range = max - min + 1;
  int count[range] = {};
  int output[n];
  for (int i = 0; i < n; i++) count[arr[i] - min]++;

  for (int i = 1; i < range; i++) count[i] += count[i - 1];

  for (int i = n - 1; i >= 0; i--) {
    output[count[arr[i] - min] - 1] = arr[i];
    count[arr[i] - min]--;
  }

  for (int i = 0; i < n; i++) arr[i] = output[i];
}

int main() {
  int n = 7;
  int arr[7] = {3, 5, 1, 1, 4, 2, 1};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  countingSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

이 구현은 음수에도 적용됩니다.

정렬 알고리즘 복잡성 계산

시간 복잡성

  • 평균 사례

계수 정렬는 모든n 항목을 두 번 반복하고 count 배열을 한 번 반복합니다. 따라서 시간 복잡도는O(n + b)이며b는 입력 범위입니다. b는 종종 작기 때문에 계수 정렬의 시간 복잡도는 [Big Theta] : O(n)의 순서라고합니다.

  • 최악의 경우

최악의 시간 복잡도는 [Big O] :O(n)입니다.

  • 베스트 케이스

최적의 시간 복잡도는 [Big Omega] :O(n)입니다. 최악의 시간 복잡성과 동일합니다.

공간 복잡성

계산 정렬 알고리즘의 공간 복잡도는O(n + b)이며 여기서b는 입력 범위입니다. 그것은count &output 배열에서 나옵니다. 때때로b는n보다 클 수 있지만 b가 작 으면 시간 복잡도는O(n)이라고합니다.

작성자 소개

Harshit Jindal

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

작성자 프로필 보기
LinkedIn