Recursive QuickSort issue...please help!

Can't get my recursive method to end...help!

Page 1 of 1

0 Replies - 1049 Views - Last Post: 28 March 2007 - 02:02 AM Rate Topic: -----

#1 lwnexgen  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 12
  • Joined: 27-March 07

Recursive QuickSort issue...please help!

Posted 28 March 2007 - 02:02 AM

Hey Guys-

I'm kind of at my wits end with this problem. I have to create a method to sort a vector into increasing order. I can get it to compile and run with a few initial vectors, but I run into a StackOverflow sometimes, meaning my recursion isn't closing right at some point in my method.

For instance, the input <1,3,2,5,4> works correctly. <1,5,3,4,2> does not, however.

Here is my code right now (its a very ugly version of the QuickSort algorithm):

public void sort(Vector<Integer> v)
	{
		Vector<Integer> less = new Vector<Integer>();
		Vector<Integer> equal = new Vector<Integer>();
		Vector<Integer> greater = new Vector<Integer>();

		v = sort(v,0,v.size()-1,v.size()/2,less,equal,greater);
	} // end of sort method
	
		private Vector<Integer> sort(Vector<Integer> v, int start, int end, int pivot, Vector<Integer> less,Vector<Integer> equal,Vector<Integer> greater)
	{
		System.out.println(v);
		if (start == v.size())
		{
			return v;
		}

		if (pivot - 1 <=0)
		{
			return v;
		}
		
		int pivotVal = v.get(pivot-1);
		
		if (v.get(start)< pivotVal)
		{
			less.add(0,v.get(start));
			sort(v,start+1,end, pivot,less,equal,greater);
		}
		else if (v.get(start)>pivotVal)
		{
			greater.add(0,v.get(start));
			sort(v,start+1,end, pivot,less,equal,greater);
		}
		else if (v.get(start)==pivotVal)
		{
			equal.add(0,v.get(start));
			sort(v,start+1,end, pivot,less,equal,greater);
		}

		v.clear();
		v.addAll(sort(less,0,less.size()-1,less.size()/2,less,equal,greater));
		v.addAll(equal);
		v.addAll(sort(greater,0,greater.size()-1,greater.size()/2,less,equal,greater));
		return v;
	}



Thanks in advance for any help you can give!

This post has been edited by lwnexgen: 28 March 2007 - 10:28 AM


Is This A Good Question/Topic? 0
  • +

Page 1 of 1