partial_sort

Article
03/26/2013

Réorganise un nombre spécifié d'éléments plus petits dans une plage dans une commande nondescending ou selon un critère de classement spécifié par un attribut 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 d'accès aléatoire adressant la position du premier élément dans la plage à trier.
sortEnd
Un itérateur d'accès aléatoire adressant une position au delà de le dernier élément dans la sous-plage à trier.
last
Un itérateur d'accès aléatoire adressant une position au delà de le dernier élément dans la plage à trier partielle.
comp
Objet défini par l'utilisateur de fonction de prédicat qui définit le critère de comparaison à répondre par des éléments consécutifs dans l'ordre.Un attribut binaire accepte deux arguments et retourne true si satisfaite et false une fois pas de contenu.

Notes

l'intervalle référencé doit être valide ; tous les pointeurs doivent être deréférençables et dans la séquence la dernière position est accessible dès le début par l'augmentation.

Les éléments sont identiques, mais pas nécessairement égales, si aucune n'est inférieure à l'autre.L'algorithme de tri stable n'est pas et ne garantit pas que le classement relatif des éléments équivalents est conservé.L'algorithme stable_sort conserve ce classement d'origine.

La complexité moyenne partielle de tri est O(last(-)firstjournal (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;
}