Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

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.

Fonti