Ordenamiento por Cubeta (Counting Sort)

La idea: contar en vez de comparar

Todos los algoritmos que hemos visto comparan elementos entre sí. Counting Sort toma un enfoque completamente diferente: no compara. En su lugar, cuenta cuántas veces aparece cada valor.

Analogía: Imagina que tienes 100 canicas de colores (rojo, azul, verde, amarillo) y quieres ordenarlas por color. En lugar de comparar canicas una por una, simplemente cuentas: 25 rojas, 30 azules, 20 verdes, 25 amarillas. Luego pones primero las 20 verdes, luego las 25 amarillas, etc. ¡No necesitaste comparar ninguna!

El algoritmo paso a paso

Con el arreglo [4, 2, 2, 8, 3, 3, 1] y valores entre 0 y 9:

Paso 1: Contar frecuencias

Valor:      0  1  2  3  4  5  6  7  8  9
Frecuencia: 0  1  2  2  1  0  0  0  1  0

Paso 2: Reconstruir el arreglo ordenado

1 aparece 1 vez  → [1]
2 aparece 2 veces → [1, 2, 2]
3 aparece 2 veces → [1, 2, 2, 3, 3]
4 aparece 1 vez  → [1, 2, 2, 3, 3, 4]
8 aparece 1 vez  → [1, 2, 2, 3, 3, 4, 8]

¡Ordenado!

Implementación

void countingSort(vector<int> &v) {
    if (v.empty()) return;

    int maxVal = *max_element(v.begin(), v.end());
    int minVal = *min_element(v.begin(), v.end());

    int rango = maxVal - minVal + 1;
    vector<int> freq(rango, 0);

    // Paso 1: Contar
    for (int x : v) {
        freq[x - minVal]++;
    }

    // Paso 2: Reconstruir
    int idx = 0;
    for (int i = 0; i < rango; i++) {
        while (freq[i] > 0) {
            v[idx] = i + minVal;
            idx++;
            freq[i]--;
        }
    }
}

Versión simple (cuando los valores son no negativos y pequeños)

void countingSort(vector<int> &v, int maxVal) {
    vector<int> freq(maxVal + 1, 0);

    for (int x : v) freq[x]++;

    int idx = 0;
    for (int val = 0; val <= maxVal; val++) {
        for (int j = 0; j < freq[val]; j++) {
            v[idx++] = val;
        }
    }
}

Complejidad

• Tiempo: $O(n + k)$ donde $n$ es el número de elementos y $k$ es el rango de valores.
• Espacio: $O(k)$ para el arreglo de frecuencias.

Esto es mucho más rápido que $O(n \log n)$... pero solo cuando $k$ es razonable. Si los valores van de 0 a mil millones, necesitarías un arreglo de mil millones de posiciones: ¡imposible!

¿Cuándo usar Counting Sort?

Aplicaciones prácticas

1. Encontrar el elemento más frecuente

int n;
cin >> n;

int freq[100001] = {0};
int maxFreq = 0, moda = 0;

for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    freq[x]++;
    if (freq[x] > maxFreq) {
        maxFreq = freq[x];
        moda = x;
    }
}

cout << "El valor " << moda << " aparece " << maxFreq << " veces" << endl;

2. Ordenar calificaciones (0-100)

int n;
cin >> n;

int freq[101] = {0};
for (int i = 0; i < n; i++) {
    int cal;
    cin >> cal;
    freq[cal]++;
}

for (int cal = 100; cal >= 0; cal--) {
    for (int j = 0; j < freq[cal]; j++) {
        cout << cal << " ";
    }
}

3. Verificar si dos arreglos son anagramas

bool sonAnagramas(vector<int> &a, vector<int> &b) {
    if (a.size() != b.size()) return false;

    int freq[100001] = {0};
    for (int x : a) freq[x]++;
    for (int x : b) freq[x]--;

    for (int i = 0; i <= 100000; i++) {
        if (freq[i] != 0) return false;
    }
    return true;
}

Ejercicio de práctica

Lee N números entre 1 y 1000. Muestra cuántos números distintos hay y cuál es el más frecuente.

Entrada:

8
3 1 4 1 5 9 2 6

Salida:

Distintos: 7
Mas frecuente: 1 (2 veces)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int freq[1001] = {0};
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        freq[x]++;
    }

    int distintos = 0;
    int maxFreq = 0, moda = 0;

    for (int i = 1; i <= 1000; i++) {
        if (freq[i] > 0) distintos++;
        if (freq[i] > maxFreq) {
            maxFreq = freq[i];
            moda = i;
        }
    }

    cout << "Distintos: " << distintos << endl;
    cout << "Mas frecuente: " << moda << " (" << maxFreq << " veces)" << endl;

    return 0;
}

Siguiente paso

Aprende sobre Recursión para resolver problemas dividiéndolos en versiones más pequeñas de sí mismos.