계수 정렬

1. 계산 정렬 알고리즘
2. 계산 정렬 예
3. 계산 정렬 알고리즘 구현
4. 정렬 알고리즘 복잡성 계산

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

계산 정렬 알고리즘

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

계산 정렬 예

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

• maxm = 7
• minm = 2
• 범위= 6
• count와output은 0으로 초기화됩니다.

• 모든 요소의 개수를 계산 한 후count 배열.

• 요소의 합을 누적 한 후count 배열.

• 첫 번째 반복 :A[7] = 2

• 두 번째 반복 :A[6] = 4

• 세 번째 반복 :A[5] = 5

• 네 번째 반복 :A[4] = 4

• 다섯 번째 반복 :A[3] = 7

• 여섯 번째 반복 :A[2] = 2

• 일곱 번째 반복 :A[1] = 3

• 여덟 번째 반복 :A[0] = 6

마지막으로 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)이라고합니다.