quickSelect

Function

template <typename ForwardIterator>
ForwardIterator quickSelect( ForwardIterator first, ForwardIterator last, const int k );

template <typename ForwardIterator, typename Compare>
ForwardIterator quickSelect( ForwardIterator first, ForwardIterator last, const int k, Compare comp );

A randomized algorithm that returns an iterator pointing to an element with value equals to the k-th smallest element in the range [first,last). The comparison is done using operator< for the first version, or comp for the second. This function will not change the items in range.

Parameters

first, last

Forward iterators to the initial and final positions of the sequence. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

k

The k-th smallet element in the range [first,last) to be returned.

comp

Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.

Return Value

Returns an iterator pointing to an element with value equal to the k-th smallest element in the range [first,last). The comparison is done using operator< for the first version, or comp for the second. If k is not between 1 and the number of items, which are between first and last, last will be returned.

Example

#include <iostream>
#include <vector>
#include "HKUAL_order.h"
using namespace std;
using namespace HKUAL;

class Compare {
  public:
    bool operator() ( int a, int b ) {
        return( a > b );
    }
};

int main() {
   int k = 3;
   
   int myints[] = { 103, 101, 109, 108, 105, 102, 107, 104, 106 };
   int* ptr = quickSelect( myints, myints + sizeof( myints ) / sizeof( int ), k );
   if( ptr == myints + sizeof( myints ) / sizeof( int ) ) {
       cout << "Invalid k, k is out of bound!!" << endl;
   }
   else {
       cout << "The k-th element is " << *ptr << endl;
   }
   
   vector<int> S( myints, myints + sizeof( myints ) / sizeof( int ) );
   vector<int>::iterator itr = quickSelect( S.begin(), S.end(), k );
   if( itr == S.end() ) {
       cout << "Invalid k, k is out of bound!!" << endl;
   }
   else {
       cout << "The k-th element is " << *itr << endl;
   }
   
   Compare comp;
   vector<int>::iterator itr2 = quickSelect( S.begin(), S.end(), k, comp );
   if( itr2 == S.end() ) {
       cout << "Invalid k, k is out of bound!!" << endl;
   }
   else {
       cout << "The k-th element is " << *itr2 << endl;
   }
   
   return( 0 );
}

Output

Complexity

The expected time complexity of this randomized algorithm is