Counting sort (ordenación por cuentas)

from collections import namedtuple

Persona = namedtuple("Persona", "nombre edad")


def por_edad(p, maximo):
    """Ordena por edad (de 0 a maximo) contando: estable y sin comparar a nadie con nadie."""
    cuenta = [0] * (maximo + 1)
    for x in p:                                 # 1. cuántos hay de cada edad
        cuenta[x.edad] += 1
    for e in range(1, maximo + 1):              # 2. cuántos con esa edad o menos
        cuenta[e] += cuenta[e - 1]
    res = [None] * len(p)
    for x in reversed(p):                       # 3. colocar, recorriendo al revés
        cuenta[x.edad] -= 1                     #    para que sea estable
        res[cuenta[x.edad]] = x
    return res


p = [Persona("Ana", 31), Persona("Luis", 25), Persona("Eva", 31), Persona("Pablo", 19), Persona("Marta", 25)]
for x in por_edad(p, 120):
    print(x.edad, x.nombre)

/** Ordena por edad (de 0 a max) contando: estable y sin comparar a nadie con nadie. */
function porEdad(p, max) {
    const cuenta = new Array(max + 1).fill(0);
    for (const x of p) cuenta[x.edad]++;                          // 1. cuántos hay de cada edad
    for (let e = 1; e <= max; e++) cuenta[e] += cuenta[e - 1];    // 2. cuántos con esa edad o menos
    const res = new Array(p.length);
    for (let i = p.length - 1; i >= 0; i--)                       // 3. colocar, recorriendo al revés
        res[--cuenta[p[i].edad]] = p[i];                          //    para que sea estable
    return res;
}

const p = [
    { nombre: "Ana", edad: 31 }, { nombre: "Luis", edad: 25 }, { nombre: "Eva", edad: 31 },
    { nombre: "Pablo", edad: 19 }, { nombre: "Marta", edad: 25 },
];
for (const x of porEdad(p, 120)) console.log(x.edad + " " + x.nombre);

using System;

record Persona(string Nombre, int Edad);

class Program {
    // Ordena por edad (de 0 a max) contando: estable y sin comparar a nadie con nadie.
    static Persona[] PorEdad(Persona[] p, int max) {
        int[] cuenta = new int[max + 1];
        foreach (var x in p) cuenta[x.Edad]++;                        // 1. cuántos hay de cada edad
        for (int e = 1; e <= max; e++) cuenta[e] += cuenta[e - 1];    // 2. cuántos con esa edad o menos
        var res = new Persona[p.Length];
        for (int i = p.Length - 1; i >= 0; i--)                       // 3. colocar, recorriendo al revés
            res[--cuenta[p[i].Edad]] = p[i];                          //    para que sea estable
        return res;
    }

    static void Main() {
        Persona[] p = { new("Ana", 31), new("Luis", 25), new("Eva", 31), new("Pablo", 19), new("Marta", 25) };
        foreach (var x in PorEdad(p, 120)) Console.WriteLine(
quot;{x.Edad} {x.Nombre}");
    }
}

<?php
/** Ordena por edad (de 0 a $max) contando: estable y sin comparar a nadie con nadie. */
function porEdad(array $p, int $max): array {
    $cuenta = array_fill(0, $max + 1, 0);
    foreach ($p as [$nombre, $edad]) $cuenta[$edad]++;                 // 1. cuántos hay de cada edad
    for ($e = 1; $e <= $max; $e++) $cuenta[$e] += $cuenta[$e - 1];     // 2. cuántos con esa edad o menos
    $res = array_fill(0, count($p), null);
    for ($i = count($p) - 1; $i >= 0; $i--)                            // 3. colocar, recorriendo al revés
        $res[--$cuenta[$p[$i][1]]] = $p[$i];                           //    para que sea estable
    return $res;
}

$p = [["Ana", 31], ["Luis", 25], ["Eva", 31], ["Pablo", 19], ["Marta", 25]];
foreach (porEdad($p, 120) as [$nombre, $edad]) echo "$edad $nombre\n";

def por_cifra(a, exp):
    """Counting sort estable por la cifra de valor exp (1 = unidades, 10 = decenas, 100 = centenas)."""
    cuenta = [0] * 10
    for x in a:
        cuenta[x // exp % 10] += 1
    for d in range(1, 10):
        cuenta[d] += cuenta[d - 1]
    res = [0] * len(a)
    for x in reversed(a):
        cuenta[x // exp % 10] -= 1
        res[cuenta[x // exp % 10]] = x
    a[:] = res


a = [170, 45, 75, 90, 802, 24, 2, 66]
for exp, nombre in [(1, "unidades"), (10, "decenas"), (100, "centenas")]:   # una pasada por cifra
    por_cifra(a, exp)
    print(f"Por {nombre}: {a}")

/** Counting sort estable por la cifra de valor exp (1 = unidades, 10 = decenas, 100 = centenas). */
function porCifra(a, exp) {
    const cifra = (x) => Math.floor(x / exp) % 10;
    const cuenta = new Array(10).fill(0);
    for (const x of a) cuenta[cifra(x)]++;
    for (let d = 1; d < 10; d++) cuenta[d] += cuenta[d - 1];
    const res = new Array(a.length);
    for (let i = a.length - 1; i >= 0; i--) res[--cuenta[cifra(a[i])]] = a[i];
    a.splice(0, a.length, ...res);
}

const a = [170, 45, 75, 90, 802, 24, 2, 66];
for (const [exp, nombre] of [[1, "unidades"], [10, "decenas"], [100, "centenas"]]) {   // una pasada por cifra
    porCifra(a, exp);
    console.log(`Por ${nombre}: [${a.join(", ")}]`);
}

using System;

class Program {
    // Counting sort estable por la cifra de valor exp (1 = unidades, 10 = decenas, 100 = centenas).
    static void PorCifra(int[] a, int exp) {
        int[] cuenta = new int[10];
        foreach (int x in a) cuenta[x / exp % 10]++;
        for (int d = 1; d < 10; d++) cuenta[d] += cuenta[d - 1];
        int[] res = new int[a.Length];
        for (int i = a.Length - 1; i >= 0; i--) res[--cuenta[a[i] / exp % 10]] = a[i];
        Array.Copy(res, a, a.Length);
    }

    static void Main() {
        int[] a = { 170, 45, 75, 90, 802, 24, 2, 66 };
        string[] nombre = { "unidades", "decenas", "centenas" };
        for (int exp = 1, k = 0; exp <= 100; exp *= 10, k++) {      // radix sort: una pasada por cifra
            PorCifra(a, exp);
            Console.WriteLine(
quot;Por {nombre[k]}: [{string.Join(", ", a)}]");
        }
    }
}

<?php
/** Counting sort estable por la cifra de valor $exp (1 = unidades, 10 = decenas, 100 = centenas). */
function porCifra(array &$a, int $exp): void {
    $cuenta = array_fill(0, 10, 0);
    foreach ($a as $x) $cuenta[intdiv($x, $exp) % 10]++;
    for ($d = 1; $d < 10; $d++) $cuenta[$d] += $cuenta[$d - 1];
    $res = array_fill(0, count($a), 0);
    for ($i = count($a) - 1; $i >= 0; $i--) $res[--$cuenta[intdiv($a[$i], $exp) % 10]] = $a[$i];
    $a = $res;
}

$a = [170, 45, 75, 90, 802, 24, 2, 66];
foreach ([1 => "unidades", 10 => "decenas", 100 => "centenas"] as $exp => $nombre) {   // una pasada por cifra
    porCifra($a, $exp);
    echo "Por $nombre: [" . implode(", ", $a) . "]\n";
}