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.