Java Quicksort Help [Solved]

Zython

Ok, I need to do a quicksort rotuine for my class. I have the following:

public static int quicksort(int A[], int k){
		quicksort(A, 0, A.length - 1);
		return A[k-1];
	}
	
	private static void swap(int A[], int a, int b){
		int key = A[a];
		A[a] = A[b];
		A[b] = key;
	}
	
	private static int median(int A[], int left, int right){
		int center = (left + right)/2;
		int key = 0;
		if(A[center] < A[left]){
			swap(A, left, center);
		}
		if(A[right] < A[left]){
			swap(A, left, right);
		}
		if(A[right] < A[center]){
			swap(A, center, right);
		}
		swap(A, center, right - 1);
		return A[right - 1];
	}
	
	private static void quicksort(int A[], int left, int right){
		if(left + 1 <= right){
			int pivot = median(A, left, right);
			int i = left, j = right - 1;
			for( ; ;){
				while(A[++i] <= pivot){
				}
%%				[b]while(A[--j] > pivot){[/b]
				}
				if(i < j){
					swap(A, i, j);
				}
				else{
					break;
				}
			}
			swap(A, i, right - 1);
%%%%		   [b]quicksort(A, left, i - 1);[/b]
			quicksort(A, i + 1, right);
		}
	}

The goal being to find the k-th smallest element in an array.

I also have to do one that's better suited for this purpose, what I have:'

	public static int quickersort(int A[], int k){
		quickersort(A, 0, A.length - 1, k);
		return A[k - 1];
	}
	
	private static void quickersort(int A[], int left, int right, int k){
		if(left + 1 <= right){
			int pivot = median(A, left, right);
			int i = left, j = right - 1;
			for( ; ;){
				while(A[++i] < pivot){
				}
%%				[b]while(A[--j] > pivot){[/b]
				}
				if(i < j){
					swap(A, i, j);
				}
				else{
					break;
				}
			}
			swap(A, i, right - 1);
			if(k <= i){
%%			     [b]quickersort(A, left, i - 1, k);[/b]
			}
			else if(k > i + 1){
				quickersort(A, i + 1, right, k);
			}
		}
	}

The problem is that I sometimes get an OutofBoundsIndex Exception at the lines bolded above. Can anyone tell me what I'm doing wrong? If you have any questions, feel free to ask.

Edit: Made problematic lines more visible.

Edit: Found the problem, the for loop wasn't breaking properly, changed to a while loop.

Jimmy King

The best I can suggest is use your debugger so that you can see what the value of j is when it dies and what values were passed to the method. That should tell you what case is causing the out of bounds exception so that you can make sure it doesn't happen.

If you're not using an IDE with a debugger, just stick some System.out.println() in there with the values.