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!

Zython
Registered User regular

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

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:'

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.

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.

0

## Posts

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

Jimmy Kingon