Hi, Guys
Here's an important problem I have been facing lately. My idea is to partition an array on basis of an element such that, this element has all the elements smaller than it before it and all the elements greater than it after it ... ( Similar to pivoting in Quick Sort ) ... Now I am using a inbuilt function defined in STL Algorithm header ... it's called nth_element ...
[*]Now I have a vector of size 20
vector <int> vect (20);
- Next I populate this array with random numbers.
[
generate (vect.begin(), vect.end(), rand);
[*]Next I try nth element, i deliberately want the the pivot to be the last element in the array. So I write this
nth_element (vect.begin(), (vect.end()-1), vect.end() );
but this doesn't work ... unfortunately ... in case any one has any doubts ... take this code, and run it ...
Somebody please help me .. I have thought enough but cn't figure out the bug.
///////////// [B]Code - Ready to be run[/B] //////////
#include <fstream>
#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <algorithm>
#include <string>
#include <iterator>
#include <cmath>
using namespace std;
//Global Declarations
// Structure Declarations
// Typedef's
typedef vector<int> VInt;
typedef VInt::iterator VIntItor;
class MyIntegerRand
{
public:
MyIntegerRand ( int limit ) {
this->limit = limit;
}
int operator() () {
return ( (rand() % limit) + 1 );
}
private:
int limit;
};
int main (){
time_t seed; // Generating a random Seed at start up
time (&seed);
srand ((unsigned long) seed );
VInt arr (20);
MyIntegerRand myIntegerRand (1000); // three digit numbers allowed
VIntItor start, end ;
for ( long i = 1 ; i <= 1 ; i++ ) {
generate ( arr.begin(), arr.end(), myIntegerRand );
start = arr.begin();
end = arr.end()-1; // to point to the last element
int pivotValue = *(end); // pivot being the last element in the present Array
cout << "\n\n Array before Partitioning" ;
printf ("(%d) -> ", distance (start, end+1) ) ;
copy ( start, end+1, ostream_iterator <long> (cout, " ,") );
cout << " \n Pivot chosen is " << *end ;
nth_element (start, end, end+1, less_equal <int> ());
cout << "\n Partitioning Done Array is now -> " ;
copy ( start, (end+1), ostream_iterator <long> (cout, " ,") );
cout << " \n Remember Pivot chosen was " << pivotValue ;
}
system("pause");
}///////////// Don't worry bout irrelevant details tht's just my style of coding ... //////////
I'm not sure wht am i doing wrong ... Kindly someone please help me ..
AViD
