Our new Indie Games subforum is now open for business in G&T. Go and check it out, you might land a code for a free game. If you're developing an indie game and want to post about it, follow these directions. If you don't, he'll break your legs! Hahaha! Seriously though.
Our rules have been updated and given their own forum. Go and look at them! They are nice, and there may be new ones that you didn't know about! Hooray for rules! Hooray for The System! Hooray for Conforming!

Java Quicksort Help [Solved]

ZythonZython Registered User regular
edited September 2010 in Help / Advice Forum
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.

3DS Friend Code: 4854-6465-0299 | Wii U: zython | PSN: Zaithon
Steam: pazython
Lv 100 Tauren Shaman
Zython on

Posts

  • Jimmy KingJimmy King Registered User regular
    edited September 2010
    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.

Sign In or Register to comment.