partial_sort

Articolo
03/26/2013

Dispone di un numero specificato di elementi più piccoli in un intervallo in un ordine nondescending o come un criterio di ordinamento specificato da un predicato binario.

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
   );

Parametri

first
Un iteratore di accesso casuale destinato alla posizione del primo elemento nell'intervallo da ordinare.
sortEnd
Un iteratore di accesso casuale destinato alla posizione una dopo l'elemento finale del sottosistema da ordinare.
last
Un iteratore di accesso casuale destinato alla posizione una dopo l'elemento finale nell'intervallo parzialmente da ordinare.
comp
Oggetto definito dall'utente di funzione di predicato che definisce i criteri di confronto da soddisfare gli elementi successivi in ordine.Un predicato binario accetta due argomenti e restituisce true una volta soddisfatti e false una volta non soddisfatta.

Note

l'intervallo fatto riferimento deve essere valido; tutti i puntatori devono essere dereferenceable e all'interno della sequenza dell'ultima posizione è raggiungibile da prima dall'aumento.

Gli elementi sono equivalenti, ma non necessariamente a, se non è inferiore all'altro.L'algoritmo di ordinamento non diventa stabile e non garantisce che l'ordine degli elementi equivalenti verrà mantenuto.L'algoritmo stable_sort conserva questo ordine originale.

La complessità parziale media di ordinamento è O(last(-)firstregistrosortEnd(-)first).

Esempio

// 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;
}