Ordenamiento por cuentas

1. Algoritmo de ordenamiento por cuentas
2. Ejemplo de ordenamiento por cuentas
3. Implementación del algoritmo de ordenamiento por cuentas
4. Complejidad del algoritmo de conteo

La ordenamiento por cuentas es un algoritmo de ordenación no comparativo. Ordena un array contando las ocurrencias de cada elemento único. Se hace un hash parcial del conteo de elementos únicos y luego se realizan cálculos para encontrar el índice de cada elemento en el arreglo final ordenado. Es un algoritmo bastante rápido, pero no es adecuado para grandes conjuntos de datos. Se utiliza como una subrutina dentro de Ordenamiento Radix.

Algoritmo de ordenamiento por cuentas

Supongamos que tenemos un array A[] sin ordenar que contiene n elementos.

Ejemplo de ordenamiento por cuentas

Supongamos que tenemos el array (6, 3, 2, 7, 4, 5, 4, 2). Lo ordenaremos utilizando el algoritmo de ordenamiento por cuentas.

• maxm = 7
• minm = 2
• rango = 6
• count y output se inicializan con ceros.

• array count después de calcular el recuento de todos los elementos.

• Matriz count después de la acumulación de la suma de elementos.

• Primera Iteración: A[7]=2

• Segunda Iteración: A[6]=4

• Tercera Iteración: A[5]=5

• Cuarta Iteración: A[4]=4

• Quinta Iteración: A[3]=7

• Sexta Iteración: A[2]=2

• Séptima Iteración: A[1]=3

• Octava Iteración: A[0]=6

Finalmente, almacenamos la array output dentro de A y obtenemos la array ordenada - 2, 2, 3, 4, 4, 5, 6, 7.

Implementación del algoritmo de ordenamiento por cuentas

#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";
}

Esta implementación también funciona con números negativos.

Complejidad del algoritmo de conteo

Complejidad temporal

• Caso medio

El algoritmo Counting Sort recorre todos los elementos n dos veces y recorre el array count una vez. Por lo tanto, tiene una complejidad de tiempo de O(n + b) donde b es el rango de entrada. Como b suele ser pequeño, la complejidad temporal de la ordenación por recuento es del orden de [Big Theta]: O(n).

• El peor caso

La complejidad temporal en el peor caso es [Big O]: O(n).

• Caso óptimo

La complejidad temporal en el mejor de los casos es [Big Omega]: O(n). Es la misma que la complejidad temporal del peor caso.

Complejidad espacial

La complejidad espacial del algoritmo de ordenamiento por cuentas es O(n+b), donde b es el rango de entrada. Proviene de los Arrays count y output. A veces b puede ser mayor que n, pero si b es pequeño, se dice que la complejidad temporal es de O(n).