Issues with quicksort

[zevlramos]

Hey everyone, I am new to the forum. I am a college student working on some homework, and I keep running into an error when trying to run my quicksort function.
We were instructed to use quicksort even on short vectors.
Can anyone see whats wrong?

void quicksort(vector<int> &v,int low, int high)
{
	int middle = ( low + high ) / 2;
	if( v[ middle ] < v[ low ] )
		swap( v[ low ], v[ middle ] );
	if( v[ high ] < v[ low ] )
		swap( v[ low ], v[ high ] );
	if( v[ high ] < v[ middle ] )
		swap( v[ middle ], v[ high ] );

	int pivot = v[middle];
	swap( v[ middle ] , v[ high-1 ]);

		
		int i,j;
		for(i=low, j=high-1; ;)
		{
			while(v[i] < pivot){i++;}
			while(pivot < v[j]){j--;}
			if(i<j)
				swap( v[ i ] , v[ j ] );
			else 
				break;
		}
	
	
	swap( v[ i ], v[ high - 1 ] );
	
	quicksort(v,low,i-1 );
	quicksort(v,i + 1,high);
		

}
	
	

void quicksort(vector<int> &v)
{
	quicksort(v,0,v.size()-1);
}

[drummin2somebeats]

I'm kinda new to this forum too, but let me help you out a bit. Try to provide as many details as possible. Saying you're having "issues" doesn't really help. Like paste in some errors you were getting and it'll help them figure it out more easily. And even then, nobody here's gonna just tell you "Here, try this code instead"

YOUR FIXED CODE

They're usually just gonna be like "Hey you should check this line, rethink it over, there might be a better way to say that". Or stuff like that. Just giving you a heads up

--
James

[simeonz]

Well, I'm not sure what error you get, so I can't help you much. But I think that one possible source of error is that you save the pivot at the end of the array, then you start search for element that is not greater than the pivot in the second half. But you will immediately run at the pivotal element itself. And you will swap it. And then, after the partition, when you try to restore the pivot to the middle of the array it will be gone from where you save it (at the end).

I am just working from the top of my head, but you can do two things:
- make the inequalities weak (v[i] <= pivot, pivot <= v[j])
- start from j = high - 2 in the partitioning loop

Regards

[zevlramos]

Thanks James, appreciate the advice!

Also thank you Simeonz, i figured that it was that once my recursive call got down to 2 elements or less, my function wasn't sure what to do with it.

[simeonz]

Oh man, how can I be so dazed. You don't have bottom for the recursion. I must be on very strong drugs or something. Still, check out what I told you. I may be wrong, but I think I am right.