Recursion help

[pocku]

I'm working on a quick sort algorithm using recursion but it's throwing a stackOverflowError. Here is the code:

public static void quicksort(int [] A){
	quickSortRec(A, 0, A.length-1);
}


public static void quickSortRec(int [] A, int p, int r){
		
	if (p < r){
		int q = Partition(A, p, r);
		quickSortRec(A, p, q-1);
		quickSortRec(A, q+1, r);	
	}
}

public static int Partition(int[] A, int p, int r){
		
	int x = A[r];
	int i = p-1;
	int j = p;
		
	while (j < r){
		if (A[j] <= x){
			i++;
			int tmp = A[i];
			A[i] = A[j];
			A[j] = tmp;
		}
		j++;
	}
	int tmp = A[i+1];
	A[i+1] = A[r];
	A[r] = tmp;
		
	return i+1;
}

The thing that's puzzling me is there's no problems when I call for it from this piece of code:

public class A5Q5 {

	public static void main(String[] args){
		
		//Length of array is given by command argument
		int length = Integer.parseInt(args[0]);
		
		//100 arrays of variable lengths of random elements are created and then sorted
		for (int i=0; i < 100; i++){
			int[] arr = new int[length];
			
			for (int j = 0; j < length; j++){
				
				Random rand = new Random();
				int n = rand.nextInt(65578);
				arr[j] = n;
			}
			try{
			Sorting.heapSort(arr);}
			catch (EmptyHeapException ex){
				System.out.println("Heap is empty, unable to sort array.");
			}
			catch (OutOfRangeException ex){
				System.out.println("Error: Out of Range");
			}
			Sorting.insertionSort(arr);
			Sorting.quicksort(arr);
			Sorting.quicksortImproved(arr);
			Arrays.sort(arr);
		}
	}
}

but a stackOverflowError is thrown when I try to call for it from this one:

public class A5Q6 {

	public static void main(String[] args){
		
		//Length of array is given by command argument
		int length = Integer.parseInt(args[0]);
		
		//100 arrays of variable lengths of elements of ascending values are created and then sorted
		for (int i=0; i < 100; i++){
			int[] arr = new int[length];
			
			int num = 0;
			for (int j = 0; j < length; j++){
				
				Random rand = new Random();
				int n = rand.nextInt(10);
				
				num += n;
				arr[j] = num;
			}
			
			try{
				Sorting.heapSort(arr);}
				catch (EmptyHeapException ex){
					System.out.println("Heap is empty, unable to sort array.");
				}
				catch (OutOfRangeException ex){
					System.out.println("Error: Index is out of range.");
				}
			Sorting.insertionSort(arr);
			Sorting.quicksort(arr);
			Sorting.quicksortImproved(arr);
			Arrays.sort(arr);
		}
	}
}

Any help will be greatly appreciated.

[pocku]

I didn't realize that I was using different command line arguments for A5Q5 and A5Q6 until now. So it seems that my code works fine for arrays of smaller lengths (such as 128) but not for arrays of larger sizes, say 16328.

[quuba]

make stack profile

[quuba]

In quickSortRec(int [] A, int p, int r) You are using array as parameter, which makes Your code most not effectively. Every call cause store whole array on the stack.

[pocku]

Alright, thanks for your help. :)

[~s.o.s~]

> Every call cause store whole array on the stack.

No it doesn't. Arrays in Java are objects and when invoking methods with object references, copy of the reference is created and copied to the stack frame which is then pushed onto the call stack [the stack which maintains the state (stack frame) of the currently executing methods]. The actual array still lives in the heap.

[neilcoffey]

On average, you really wouldn't expect to perform so many recursions as to get a stack overflow error: even with your list size of 16,000, on average, you'd expect to go to around 14 or so levels of recursion (2^14 = 16384).

But in the WORST case, quicksort will require 'n' levels of recursion, and I think you're hitting this worst case. It looks like you're sorting the data and then always using the rightmost element as the pivot value. If you do that, then if you think about it, on each recursion you're picking the highest value in the sublist as the pivot value, so that instead of splitting the list roughly into two equal halves (on average what you'd expect if you chose a random pivot position), you're splitting it into "halves" that are (n-1) and 1 in length.

To get round this you need to either:
(1) guarantee that you won't pass already-sorted data to your method, or
(2) have a better pivot selection method (common strategies are to just pick a random index each time, or perform "quick heuristic" to choose a pivot value -- e.g. take the average of the numbers at x random indices).