partial_sort

Article
06/09/2015

Organise un nombre spécifié de plus petits éléments dans une plage spécifiée dans un ordre non décroissant ou selon un critère de classement spécifié par un prédicat binaire.

template<class RandomAccessIterator>
   void partial_sort(
      RandomAccessIterator first, 
      RandomAccessIterator sortEnd,
      RandomAccessIterator last
   );
template<class RandomAccessIterator, class BinaryPredicate>
   void partial_sort(
      RandomAccessIterator first, 
      RandomAccessIterator sortEnd,
      RandomAccessIterator last
      BinaryPredicate comp
   );

Paramètres

first
Un itérateur à accès aléatoire qui adresse la position du premier élément dans la plage de tri.
sortEnd
Un itérateur à accès aléatoire qui adresse la position située un cran après l'élément final dans la sous-plage de tri.
last
Un itérateur à accès aléatoire qui adresse la position située un cran après l'élément final dans la plage à trier partiellement.
comp
Objet de la fonction de prédicat définie par l'utilisateur qui définit les critères de comparaison à satisfaire par des éléments consécutifs dans le classement. Un prédicat binaire a besoin de deux arguments. Il renvoie true lorsqu'il est satisfait et false dans le cas contraire.

Notes

La plage source triée référencée doit être valide ; tous les pointeurs doivent être deréférençables et, dans la séquence, la dernière position doit être accessible à partir de la première par incrémentation.

Les éléments sont équivalents, mais pas nécessairement égaux, si aucun n'est inférieur à l'autre. L'algorithme de tri n'est pas stable et ne garantit pas que l'ordre relatif des éléments équivalents soit conservé. L'algorithme stable_sort garde ce classement d'origine.

La complexité de tri partiel moyenne est Ylast((-)first log (sortEnd-first).

Exemple

// alg_partial_sort.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>      // For greater<int>( )
#include <iostream>

// Return whether first element is greater than the second
bool UDgreater ( int elem1, int elem2 )
{
   return elem1 > elem2;
}

int main( )
{
   using namespace std;
   vector <int> v1;
   vector <int>::iterator Iter1;

   int i;
   for ( i = 0 ; i <= 5 ; i++ )
   {
      v1.push_back( 2 * i );
   }

   int ii;
   for ( ii = 0 ; ii <= 5 ; ii++ )
   {
      v1.push_back( 2 * ii +1 );
   }

   cout << "Original vector:\n v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")" << endl;

   partial_sort(v1.begin( ), v1.begin( ) + 6, v1.end( ) );
   cout << "Partially sorted vector:\n v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")" << endl;

   // To partially sort in descending order, specify binary predicate
   partial_sort(v1.begin( ), v1.begin( ) + 4, v1.end( ), greater<int>( ) );
   cout << "Partially resorted (greater) vector:\n v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")" << endl;

   // A user-defined (UD) binary predicate can also be used
   partial_sort(v1.begin( ), v1.begin( ) + 8, v1.end( ), 
 UDgreater );
   cout << "Partially resorted (UDgreater) vector:\n v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")" << endl;
}