[lwnexgen]

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