Ordenación en C++: std::sort, comparadores personalizados y ordenación estable

Ordenar es solo otro algoritmo

En la página anterior viste que la biblioteca estándar incluye algoritmos listos para usar que funcionan sobre cualquier rango a través de iteradores. La ordenación es la que usarás con más frecuencia, y tiene su propia página porque presenta algunas aristas afiladas: órdenes personalizados, estabilidad y una regla que, si la incumples, te da comportamiento indefinido en lugar de una respuesta incorrecta.

El caballo de batalla es std::sort de <algorithm>. Le das el principio y el final de un rango, y reordena los elementos en su sitio en orden ascendente:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end());   // ascendente, en su sitio

    for (int n : nums) cout << n << " ";  // 1 2 3 5 8 9
    cout << "\n";
    return 0;
}

No se hace ninguna copia: el propio vector se reordena. Por dentro, std::sort suele ser un introsort (quicksort que recurre a heapsort), lo que te da O(n log n) de media. Eso es casi siempre más rápido y mucho menos propenso a errores que escribir tu propia ordenación.

También funciona con arrays de C puros: solo tienes que describir el rango con punteros:

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {40, 10, 30, 20};
    int n = 4;

    sort(arr, arr + n);               // o sort(begin(arr), end(arr));

    for (int x : arr) cout << x << " ";  // 10 20 30 40
    return 0;
}

Orden personalizado con un comparador

Por defecto, std::sort ordena los elementos con operator<. Para ordenar de otra forma, pasa un tercer argumento: un comparador que toma dos elementos y devuelve true si el primero debe ir antes que el segundo.

Una lambda encaja de forma natural. El orden descendente es simplemente a > b:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;   // "a antes que b" cuando a es mayor -> descendente
    });

    for (int n : nums) cout << n << " ";  // 9 8 5 3 2 1
    cout << "\n";
    return 0;
}

Para el caso habitual de orden descendente puro sobre tipos integrados, la biblioteca incluso trae un comparador listo para usar, greater<T>() de <functional>:

#include <functional>
sort(nums.begin(), nums.end(), greater<int>());  // igual que a > b

El comparador también es la forma de ordenar por algo distinto del propio valor; por ejemplo, ordenar cadenas por longitud en lugar de alfabéticamente:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    vector<string> words = {"pear", "fig", "banana", "kiwi"};

    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.size() < b.size();   // las palabras más cortas primero
    });

    for (const string& w : words) cout << w << " ";  // fig kiwi pear banana
    cout << "\n";
    return 0;
}

Recibe los parámetros del comparador por const& para cualquier cosa mayor que un par de bytes (como string): copiar cada elemento en cada comparación es puro desperdicio.

Ordenar structs por un campo

En programas reales normalmente ordenas colecciones de structs por uno de sus campos. El comparador simplemente accede al campo que te interesa. Aquí ordenamos personas por edad, del más joven primero:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Person {
    string name;
    int age;
};

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age;
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    return 0;
}

Fíjate en que Linus y Dennis tienen ambos 25 años. Aquí salieron en su orden relativo original, pero std::sort no lo garantiza. Si el orden relativo de los elementos iguales importa, usa std::stable_sort, que lo conserva (a un pequeño coste de rendimiento):

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    stable_sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) { return a.age < b.age; });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    // Linus se mantiene antes que Dennis: se conserva su orden de entrada
    return 0;
}

Para deshacer empates de forma deliberada (por ejemplo, ordenar por edad y luego alfabéticamente por nombre), compara la clave secundaria solo cuando las claves primarias sean iguales. std::tie lo deja limpio:

#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
using namespace std;

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return tie(a.age, a.name) < tie(b.age, b.name);  // edad, luego nombre
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";  // Dennis y Linus 25, alfabético
    return 0;
}

La trampa del orden débil estricto

Este es el error más peligroso al ordenar en C++, porque no te da una respuesta incorrecta: te da comportamiento indefinido, que a menudo significa una caída o una lectura fuera de los límites.

std::sort requiere que tu comparador defina un orden débil estricto. La regla práctica: comp(x, x) debe ser false para cualquier elemento x. En otras palabras, un elemento nunca está "antes" que sí mismo. Eso es exactamente lo que te dan < y >, y exactamente lo que rompen <= y >=:

// BUG: devuelve true cuando a == b, violando el orden débil estricto.
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;   // comportamiento indefinido: puede caerse con algunas entradas
});

Con <=, el comparador afirma que 5 va antes que otro 5, lo cual es contradictorio. std::sort puede entonces recorrer un puntero más allá del final del rango. Las entradas pequeñas a veces parecen funcionar, lo que hace que este bug sea aterrador: puede pasar tus pruebas y caerse en producción. La solución es simplemente <:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

    sort(v.begin(), v.end(), [](int a, int b) {
        return a < b;   // correcto: false cuando son iguales
    });

    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

Un segundo problema clásico: ordenar invalida cualquier cosa que apunte dentro del rango. Los iteradores, punteros e índices que guardaste antes de ordenar ya no se refieren al mismo elemento lógico después, porque los elementos se movieron. Vuelve a obtener cualquier posición que necesites después de ordenar, nunca antes.

Ordenar parte de un rango

A veces no necesitas ordenarlo todo: solo quieres los primeros elementos. Ordenar el vector entero para leer los tres primeros es un desperdicio. std::partial_sort organiza solo los elementos que pidas y deja el resto en un orden no especificado, lo cual es más barato:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};

    // Coloca los 3 menores, en orden, al principio. El resto queda sin especificar.
    partial_sort(v.begin(), v.begin() + 3, v.end());

    for (int i = 0; i < 3; i++) cout << v[i] << " ";  // 1 2 3
    cout << "\n";
    return 0;
}

Y si solo necesitas el único elemento que estaría en una posición dada (como la mediana), std::nth_element hace aún menos trabajo: coloca el elemento correcto en ese índice, con todo lo menor antes y todo lo mayor después, todo en O(n) de media.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    size_t mid = v.size() / 2;

    nth_element(v.begin(), v.begin() + mid, v.end());

    cout << "median is " << v[mid] << "\n";  // 5
    return 0;
}

Recurre a estos cuando "totalmente ordenado" es más de lo que el problema realmente necesita: ahorran tiempo real con datos grandes.

Siguiente: Plantillas

¿Te has fijado en que el mismo std::sort manejó int, string y tu propio struct Person, y que greater<int>() podría ser igual de fácil greater<string>()? Esa generalidad no es magia: son las plantillas, el mecanismo que permite que una sola pieza de código funcione para cualquier tipo que el llamante le pase. En la siguiente página veremos cómo escribir tus propias funciones y clases con plantillas, para que tu código pueda ser tan agnóstico respecto al tipo como los algoritmos que has estado usando.