CKTIS / C++
std::partial_sort — un prefijo ordenado de un rango
std::partial_sort selecciona los k elementos más pequeños y los coloca en un prefijo ordenado del rango. Modifica la entrada, mientras que el orden del resto de elementos no está especificado.
Versión: C++23; repository compiler flag, production runtime not attested
Sintaxis
#include <algorithm>
std::partial_sort(first, middle, last);
std::partial_sort(first, middle, last, comp);std::partial_sort, declarado en <algorithm>, produce los primeros k elementos ordenados sin ordenar todo el rango. Para k = middle - first, coloca en [first, middle) los elementos que aparecerían al principio después de ordenar el rango completo. El orden predeterminado es ascendente; la sobrecarga con comp usa el orden indicado. Devuelve void.
El algoritmo reorganiza los elementos del rango original. El orden en [middle, last) no está especificado: no des por hecho que este sufijo permanece sin cambios o queda ordenado. No se garantiza la estabilidad, por lo que los elementos equivalentes según la comparación no tienen por qué conservar su orden relativo.
Se requieren iteradores de acceso aleatorio y rangos válidos [first, middle) y [middle, last). Los elementos deben admitir intercambio, construcción por movimiento y asignación por movimiento. Antes de formar first + k, asegúrate de que 0 <= k <= last - first. El comparador debe definir un orden débil estricto; no uses <= en lugar de <.
Para N = last - first y k > 1, el número de comparaciones es aproximadamente N * log(k). Usa este algoritmo cuando necesites un subconjunto ordenado de los mejores datos. Con middle == last, se ordena todo el rango. El ejemplo solo muestra los tres elementos seleccionados, así que su salida no depende del orden no especificado del sufijo.
Ejemplos
#include <algorithm>
#include <array>
#include <iostream>
int main() {
std::array<int, 6> values{8, 3, 7, 1, 5, 2};
constexpr int k = 3;
std::partial_sort(values.begin(), values.begin() + k, values.end());
for (int i = 0; i < k; ++i) {
if (i != 0) std::cout << ' ';
std::cout << values[i];
}
std::cout << '\n';
}
Resultado
1 2 3
El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.