Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C++

std::partial_sort — um prefixo ordenado de um intervalo

std::partial_sort seleciona os k elementos mais pequenos e coloca-os num prefixo ordenado do intervalo. Modifica os dados de entrada, enquanto a ordem dos elementos restantes não é especificada.

Versão: C++23; repository compiler flag, production runtime not attested

Sintaxe

#include <algorithm>
std::partial_sort(first, middle, last);
std::partial_sort(first, middle, last, comp);

std::partial_sort, declarado em <algorithm>, produz os primeiros k elementos ordenados sem ordenar todo o intervalo. Para k = middle - first, coloca em [first, middle) os elementos que apareceriam no início após uma ordenação completa. A ordem predefinida é crescente; a sobrecarga com comp utiliza a ordem indicada. Devolve void.

O algoritmo reorganiza os elementos no intervalo original. A ordem em [middle, last) não é especificada: não assumas que este sufixo permanece inalterado ou fica ordenado. A estabilidade não é garantida; por isso, elementos equivalentes segundo a comparação não têm necessariamente de manter a sua ordem relativa.

São necessários iteradores de acesso aleatório e intervalos válidos [first, middle) e [middle, last). Os elementos têm de permitir troca, construção por movimento e atribuição por movimento. Antes de formar first + k, garante que 0 <= k <= last - first. O comparador tem de definir uma ordem fraca estrita; não uses <= em vez de <.

Para N = last - first e k > 1, o número de comparações é aproximadamente N * log(k). Utiliza este algoritmo quando precisares de um subconjunto ordenado dos melhores dados. Com middle == last, todo o intervalo fica ordenado. O exemplo apresenta apenas os três elementos selecionados, pelo que o resultado não depende da ordem não especificada do sufixo.

Exemplos

#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

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.

Fontes