partial_sort

Artikel
06/09/2015

Ordnet eine angegebene Anzahl kleinerer Elemente in einem Bereich in eine nondescending Reihenfolge oder entsprechend einem Sortierkriterium an, das durch ein binäres Prädikat angegeben wird.

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

Parameter

first
Ein Iterator mit wahlfreier Zugriff, der die Position des ersten Elements im Bereich behandelt sortiert werden.
sortEnd
Ein Iterator mit wahlfreier Zugriff, der die Position eine hinter dem letzten Element im Unterbereich behandelt sortiert werden.
last
Ein Iterator mit wahlfreier Zugriff, der die Position eine hinter dem letzten Element im Bereich behandelt, teilweise sortiert werden.
comp
Benutzerdefiniertes Prädikatfunktionsobjekt, das definiert durch aufeinander folgende Elemente in der Bestellung erfüllt werden Vergleichskriterium. Ein binärer Prädikat akzeptiert zwei Argumente und gibt bei Erfüllung true zurück und false, wenn es nicht erfüllt wird.

Hinweise

Der Bereich, auf den verwiesen wird, gültig sein; muss alle Zeiger müssen dereferenzierbar befinden der Sequenz ist die letzte Position der ersten von Zunahme erreichbar.

Elemente sind äquivalent, aber entsprechen nicht unbedingt, wenn nicht geringer als die andere. Der sort Algorithmus ist nicht stabil und garantiert nicht, dass die relative Position der entsprechenden Elemente beibehalten wird. Der Algorithmus stable_sort behält diese ursprüngliche Reihenfolge bei.

Die durchschnittliche partielle Sortierungskomplexität ist O((last-first) Protokoll (sortEnd-first).

Beispiel

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