Cómo ordenar en la biblioteca de plantillas estándar (STL) de C++

Usa la función sort() de la biblioteca estándar de C++, de <algorithm>, para ordenar un array o un vector en su lugar. Por defecto, ordena el rango semiabierto desde first hasta, pero sin incluir, last en orden ascendente. Pasa un comparador para elegir otro orden.

Usar la función sort() para ordenar un array o un vector en C++

std::sort acepta iteradores de acceso aleatorio, por lo que funciona con arrays y vectores. No puede reordenar std::set o std::map en su lugar porque esos contenedores no proporcionan iteradores de acceso aleatorio. Este programa completo ordena tanto un array como un vector:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    int values[] = {8, 3, 6, 1, 5};
    std::vector<int> scores{14, 7, 22, 9};

    std::sort(std::begin(values), std::end(values));
    std::sort(scores.begin(), scores.end());

    for (int value : values) std::cout << value << ' ';
    std::cout << '\n';
    for (int score : scores) std::cout << score << ' ';
    std::cout << '\n';
    return 0;
}

std::begin y std::end proporcionan el rango del array, mientras que el vector usa sus iteradores begin() y end(). Este programa se proporciona como un ejemplo no ejecutado; su salida se omite hasta que se observe en el entorno de ejecución configurado. Ambas llamadas modifican los elementos originales, por lo que el código posterior los ve en el nuevo orden. Para ordenar solo una parte de un contenedor, pasa iteradores que delimiten esa porción.

Ordenar un array o un vector en orden descendente en C++

Pasa std::greater<> como tercer argumento para ordenar los valores de mayor a menor. Incluye <functional> para el comparador. Por ejemplo, std::sort(values.begin(), values.end(), std::greater<>{}); ordena un vector en orden descendente. El comparador cambia la regla de ordenación sin cambiar qué rango se ordena.

Usar partial_sort() para ordenar parte de un array o un vector

Usa partial_sort(first, middle, last) cuando solo un prefijo debe estar ordenado. Coloca los middle - first elementos más pequeños en orden antes de middle. No se garantiza ningún orden particular para los elementos de middle a last. Por ejemplo, std::partial_sort(values.begin(), values.begin() + 3, values.end()); selecciona los tres valores más pequeños para las tres primeras posiciones.

Usar un comparador personalizado con sort() en C++

Un comparador te permite ordenar valores por una clave como la longitud de la cadena. Por ejemplo, std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) { return a.size() < b.size(); }); coloca las cadenas más cortas primero. Un comparador debe definir un orden débil estricto: debe ser consistente y no debe considerar que un elemento precede a sí mismo. Las cadenas con igual longitud son equivalentes bajo esta comparación, por lo que su orden relativo no está especificado. Incluye <string> junto con <algorithm> al usar este ejemplo.

Comprobar si un rango está ordenado con is_sorted()

std::is_sorted(first, last) devuelve true cuando el rango desde first hasta, pero sin incluir, last está ordenado según la comparación por defecto, y false en caso contrario. Comprueba el rango sin reordenar sus elementos. Proporciona el mismo comparador usado para un orden personalizado al comprobar ese orden, como en std::is_sorted(words.begin(), words.end(), compare).

Complejidad temporal de los algoritmos de ordenación

Para std::sort, el estándar especifica O(N log N) comparaciones en el peor caso, donde N es el número de elementos del rango. Esto describe cómo crece el trabajo con la longitud del rango; no promete una implementación de ordenación particular. std::partial_sort usa aproximadamente N log K comparaciones al seleccionar y ordenar K elementos de N, mientras que std::is_sorted realiza como máximo N - 1 comparaciones. Estos límites ayudan a distinguir entre ordenar completamente un rango, ordenar solo un prefijo o comprobar un orden existente.