CKTIS / C++
std::partial_sort — un prefisso ordinato di un intervallo
std::partial_sort seleziona i k elementi più piccoli e li colloca in un prefisso ordinato dell’intervallo. Modifica i dati di ingresso, mentre l’ordine degli elementi rimanenti non è specificato.
Versione: C++23; repository compiler flag, production runtime not attested
Sintassi
#include <algorithm>
std::partial_sort(first, middle, last);
std::partial_sort(first, middle, last, comp);std::partial_sort, dichiarato in <algorithm>, produce i primi k elementi ordinati senza ordinare l’intero intervallo. Per k = middle - first, colloca in [first, middle) gli elementi che comparirebbero all’inizio dopo un ordinamento completo. L’ordine predefinito è crescente; l’overload con comp usa l’ordinamento specificato. Restituisce void.
L’algoritmo riordina gli elementi nell’intervallo originale. L’ordine in [middle, last) non è specificato: non presumere che questo suffisso resti invariato o venga ordinato. La stabilità non è garantita, quindi gli elementi equivalenti secondo il confronto non devono necessariamente mantenere il loro ordine relativo.
Sono richiesti iteratori ad accesso casuale e intervalli validi [first, middle) e [middle, last). Gli elementi devono supportare lo scambio, la costruzione per spostamento e l’assegnazione per spostamento. Prima di formare first + k, assicurati che 0 <= k <= last - first. Il comparatore deve definire un ordine debole stretto; non usare <= al posto di <.
Per N = last - first e k > 1, il numero di confronti è approssimativamente N * log(k). Usa questo algoritmo quando ti serve un sottoinsieme ordinato dei migliori dati. Con middle == last, viene ordinato l’intero intervallo. L’esempio stampa solo i tre elementi selezionati, quindi l’output non dipende dall’ordine non specificato del suffisso.
Esempi
#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';
}
Risultato
1 2 3
Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.