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

line 44: you need to include <ctime>

Otherwise this is what I get. Is it right or wrong? I'm not certain what your code is trying to do but from the looks of the output it looks like you are trying to sort the array

Array before Partitioning(20) -> 943 ,693 ,788 ,192 ,708 ,138 ,116 ,465 ,853 ,2
35 ,754 ,614 ,992 ,425 ,953 ,221 ,758 ,674 ,392 ,242 ,
Pivot chosen is 242
Partitioning Done Array is now -> 116 ,138 ,192 ,221 ,235 ,242 ,392 ,425 ,465 ,
614 ,674 ,693 ,708 ,754 ,758 ,788 ,853 ,943 ,953 ,992 ,
Remember Pivot chosen was 242Press any key to continue . . .

line 44: you need to include <ctime>

Otherwise this is what I get. Is it right or wrong? I'm not certain what your code is trying to do but from the looks of the output it looks like you are trying to sort the array

See I'm just trying to partition the array [Kindly refer to the nth_partition to see what it does ], in the output you have shown, it somehow worked, but it doesn't always work the same way, I mean the right way. It is a strange behavior indeed.

okay, again Imagine I have a vector of size 20 and call it vect .... that is it's declared as

vector <long> vect (20);
generate (vect.start(), vect.end(), rand);
nth_element (vect.start(), vect.end()-1, vect.end() ); // What do you think this line will do ?

As I write this code, the third line should consider last element (pointed to by vect.end()-1 iterator) and partition the vector in the manner nth_element is suppose to (Similar to pivoting operation in QuickSort ). But it doesn't seem to work, always ... tht's the problem I'm getting.


AViD

I have analysed your code and finds that the nth_element works as it should, I tested it on VC++ 2005 and VC++ 2008.
After changing the code you suggested

for ( long i = 1 ; i <= 1 ; i++ ) {	
		
		generate	( arr.begin(), arr.end(), myIntegerRand );
		
		start 	 = arr.begin();
		end	= arr.end();            // to point to the last element
		
		int pivotValue = *(end-1);	// pivot being the last element in the present Array
		
		cout << "\n\n Array before Partitioning" ; 
		printf ("(%d) -> ", distance (start, end) ) ;
		copy ( start, end, ostream_iterator <long> (cout, " ,") );
		cout <<  " \n Pivot chosen is " << pivotValue ;
		
		nth_element (start, end-1, end, less_equal <int> ());
    	
		 cout << "\n Partitioning Done Array is now -> " ;
		copy ( start, end, ostream_iterator <long> (cout, " ,") );
		cout <<  " \n Remember Pivot chosen was " << pivotValue ;

	}

it still works fine, I think you are doing some mistak while doing some iterator arithmatic.
[bold]end () points to one past last element not the last element.[/bold]
Explain if its not your problem.

I increased the array size from 20 to 100 and the program crashes most of the time on the line nth_element (start, end, end+1, less_equal <int> ()); When I change it to this it works every time nth_element (arr.begin(), arr.end()-1, arr.end());

After carefully checking the Anciant dragons comments I checked again, and Find that, It works as it should when the following is used.

nth_element (arr.begin (), arr.end()-1, arr.end (), less<int>());

Check to see if it really works.
and tell me why you use the less_equal ?

I have analysed your code and finds that the nth_element works as it should, I tested it on VC++ 2005 and VC++ 2008.
After changing the code you suggested

for ( long i = 1 ; i <= 1 ; i++ ) {	
		
		generate	( arr.begin(), arr.end(), myIntegerRand );
		
		start 	 = arr.begin();
		end	= arr.end();            // to point to the last element
		
		int pivotValue = *(end-1);	// pivot being the last element in the present Array
		
		cout << "\n\n Array before Partitioning" ; 
		printf ("(%d) -> ", distance (start, end) ) ;
		copy ( start, end, ostream_iterator <long> (cout, " ,") );
		cout <<  " \n Pivot chosen is " << pivotValue ;
		
		nth_element (start, end-1, end, less_equal <int> ());
    	
		 cout << "\n Partitioning Done Array is now -> " ;
		copy ( start, end, ostream_iterator <long> (cout, " ,") );
		cout <<  " \n Remember Pivot chosen was " << pivotValue ;

	}

it still works fine, I think you are doing some mistak while doing some iterator arithmatic.
[bold]end () points to one past last element not the last element.[/bold]
Explain if its not your problem.

See you are absolutely right, that end() points to one past the last element, tht's why nth iterator should point to end()-1, if i want partitioning to be done considering last element in the array. But it fails to work, though sometimes it works.

Note however, that though the nth iterator should point to end()-1 [ second argument to the function ] the last iterator should be end() only ....

I know it works, but tht's a random behavior, sometimes it works and other times it doesn't ...


AViD

After carefully checking the Anciant dragons comments I checked again, and Find that, It works as it should when the following is used.

nth_element (arr.begin (), arr.end()-1, arr.end (), less<int>());

Check to see if it really works.
and tell me why you use the less_equal ?

okay, Friend, I followed your advice, and used less<int>() instead of less_equal<int>(), but it still doesn't work. To be mighty honest, I have almost gone crazy with the code, I dn't know what the hell to do ... I'm slowly dying thinking too much ... Plz help ..

The latest Code I'm pasting is this ...

#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
		
	for ( long i = 1 ; i <= 1; i++ ) {
		
		
		generate ( arr.begin(), arr.end(), myIntegerRand );
		int pivotValue = *(arr.end()-1); // pivot being the last element in the present Array
	
		cout << "\n\n Array before Partitioning " ;	printf ("(%d) -> ", distance (arr.begin(), arr.end()) ) ;
		copy ( arr.begin(), arr.end(), ostream_iterator <int> (cout, " ,") );
		cout << " \n Pivot chosen is " << *(arr.end()-1) ;

	
		nth_element (arr.begin(), (arr.end()-1), arr.end(), less<int>());
		VIntItor pivot = find (arr.begin(), arr.end(), pivotValue);
		assert (*pivot == pivotValue);
		
//		if 	( 	( find_if ( arr.begin(), pivot, bind2nd(greater<int>(), *pivot) ) == pivot ) 
//			 						 		|| 
//				( find_if (pivot+1, arr.end(), bind2nd (less<int>(), *pivot) ) == arr.end() )
//			) {
//				printf ("\n\n\n Remember that here partitioning has failed for pivot = %d\n", *pivot);
//				copy ( arr.begin(), arr.end(), ostream_iterator <long> (cout, " ,") );
//		}
		
		cout << "\n Partitioning Done Array is now -> " ;
		copy ( arr.begin(), arr.end(), ostream_iterator <long> (cout, " ,") );
		cout << " \n Remember Pivot chosen was " << pivotValue ;
	}
	cout << endl ; system("pause");
	
	}

Nybody please, Help Please !!!!

AViD

Aren't you getting any compile errors ? I compile that code with VC++ 2008 Express and get an error that time() is undefined, and that is because you failed to include <ctime> header file.

This is the output I get

Array before Partitioning (20) -> 654 ,383 ,112 ,300 ,132 ,721 ,447 ,795 ,601 ,
115 ,335 ,726 ,395 ,386 ,542 ,624 ,292 ,555 ,713 ,930 ,
Pivot chosen is 930
Partitioning Done Array is now -> 112 ,115 ,132 ,292 ,300 ,335 ,383 ,386 ,395 ,
447 ,542 ,555 ,601 ,624 ,654 ,713 ,721 ,726 ,795 ,930 ,
Remember Pivot chosen was 930
Press any key to continue . . .

If you don't get that then tell me what compile your are using. Are you using MS-Windows, *nix MAC, or what?

>>nth_element (arr.begin(), (arr.end()-1), arr.end(), less<int>());

It isn't even necessary to specify that last parameter -- for your purpose just use the default nth_element (arr.begin(), (arr.end()-1), arr.end());

Aren't you getting any compile errors ? I compile that code with VC++ 2008 Express and get an error that time() is undefined, and that is because you failed to include <ctime> header file.

This is the output I get


If you don't get that then tell me what compile your are using. Are you using MS-Windows, *nix MAC, or what?

>>nth_element (arr.begin(), (arr.end()-1), arr.end(), less<int>());

It isn't even necessary to specify that last parameter -- for your purpose just use the default nth_element (arr.begin(), (arr.end()-1), arr.end());

No i didn't include ctime() and I didn't get any compile time errors or warnings..... I know the last parameter is optional, but still whether I include it or not, is immaterial and answer screws up even then. I am using Win Xp Sp2, Dev C++ 4.9.9.2.

The answer that you are showing, is somehow lucky if u'll run this code a multiple times, than it's sure to give wrong results, at least in DevC++ .....

Nyways, Thank you very very much, for trying to figure out the bug. It's really a bad one and undoubtedly frustrating one.


AViD

I found this regarding nth_element behavior on VC++ 2005.

http://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=170789

I think the microsoft implementation has the bug with predicate version of nth_element.

Yaa, I read tht, but the main problem is tht why is my code not working, I am Dev C++ 4.9.9 under windows Xp Sp2. I really dn't know wht the hell is wrong here. Anyways, Thank you for helping me out here, I really appreciate ur time and effort.


AViD

I just compiled with Dev-C++ and you are right -- it does screw up. The data is not sorted. I again ran it 20 times with VC++ 2008 Express and it worked correctly every time.

Conclusion: Dev-C++ is broken. It is beta afterall :) Use VC++ 2008 Express to save yourself a lot of unnecessary headaches.

This article has been dead for over six months. Start a new discussion instead.