partial_sort

Sort the smallest N elements of a sequence.

Sort the first n elements in the range [ first ... last ) where N = middle - first . The remaining elements in the range [ first ... last ) are placed in an undefined order in the range [ middle ... last ). The first version performs the sort using operator< , whereas the second version uses the binary function compare .

Library

Standards<ToolKit>

Declaration


#include <algorithm>

template< class RandomAccessIterator >
void partial_sort
  (
  RandomAccessIterator first,
  RandomAccessIterator middle,
  RandomAccessIterator last
  );

template< class RandomAccessIterator, class Compare >
void partial_sort
  (
  RandomAccessIterator first,
  RandomAccessIterator middle,
  RandomAccessIterator last,
  Compare compare
  );

Complexity

Time complexity is ( last - first ) * log ( n ). Space complexity is constant.

Example <ospace/osstd/examples/parsrt0.cpp>
#include <iostream>
#include <algorithm>

int numbers[ 6 ] = { 5, 2, 4, 3, 1, 6 };

void
main()
  {
  partial_sort( numbers, numbers + 3, numbers + 6 );

  for ( int i = 0; i < 6; ++i )
    cout << numbers[ i ] << ` `;
  cout << "\n";
  }

1 2 3 5 4 6
Example <ospace/osstd/examples/parsrt1.cpp>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <iterator>
#include <vector>

void
main()
  {
  vector< int > v1( 10 );
  for ( int i = 0; i < v1.size(); ++i )
    v1[ i ] = rand() % 10;
  ostream_iterator< int > iter( cout, " " );
  copy( v1.begin(), v1.end(), iter );
  cout << "\n";

  partial_sort( v1.begin(), v1.begin() + v1.size() / 2, v1.end() );

  copy( v1.begin(), v1.end(), iter );
  cout << "\n";
  }

6 0 2 0 6 7 5 5 8 6
0 0 2 5 5 7 6 6 8 6
Example <ospace/osstd/examples/parsrt2.cpp>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <iterator>
#include <vector>

char* names[] = { "aa", "ff", "dd", "ee", "cc", "bb" };

bool
str_compare( const char* a_, const char* b_ )
  {
  return ::strcmp( a_, b_ ) < 0 ? 1 : 0;
  }

void
main()
  {
  const unsigned nameSize = sizeof( names ) / sizeof( names[ 0 ] );
  vector< char* > v1( nameSize );
  for ( int i = 0; i < v1.size(); ++i )
    v1[ i ] = names[ i ];
  ostream_iterator< char* > iter( cout, " " );
  copy( v1.begin(), v1.end(), iter );
  cout << "\n";

  partial_sort
    (
    v1.begin(),
    v1.begin() + nameSize / 2,
    v1.end(),
    str_compare
    );

  copy( v1.begin(), v1.end(), iter );
  cout << "\n";
  }

aa ff dd ee cc bb
aa dd ff ee cc bb

Copyright©1994-2026 Recursion Software LLC
All Rights Reserved - For use by licensed users only.