# QuickSelect Help

• April 12th, 2013, 10:14 AM
3sbwya
QuickSelect Help
I'm work on the quickSelect algorithm to find the kth smallest integer however I keep getting the java.lang.ArrayIndexOutOfBoundsException error.

Code java:

```import java.io.*; import java.lang.ArrayIndexOutOfBoundsException; import java.util.Random;   public class QSelect {   public static void main(String[] args){ int n = 16; int[] array = new int[n]; Random random = new Random();   for(int i = 0; i < n; i++){ array[i] = random.nextInt(33); }   int k = array.length/2;   System.out.println(java.util.Arrays.toString(array)); System.out.println("K = " + k + "\n");   int count = quickSelect(array, 0, array.length-1, k); }   static int quickSelect(int[] array, int low, int high, int k){ int i = low, j = high; int count = 0;   int p = array[low + (high-low)/2]; int pivotIndex = low + (high-low)/2;   System.out.println("Pivot: " + p); // Divide into two lists while (i <= j) {   //i increments until it is greater than the pivor   while (array[i] < p) { i++; count++; }   //j decrements untili it is smaller than   while (array[j] > p) { j--; count++; }   /* * When the elements in i are greater or equal to j * they swap values */ count++; if (i <= j) { System.out.println("Swapping " + i + " and " + j);   //keeps track of pivot position if(i == pivotIndex){ pivotIndex = j; } else if(j == pivotIndex){ pivotIndex = i; }   swap(array, i, j, pivotIndex); System.out.println("Pivot Index: " + pivotIndex); i++; j--; } System.out.println(java.util.Arrays.toString(array)); } System.out.println("Pivot Index: " + pivotIndex);   if(pivotIndex == k-1) System.out.println(p + " is the kth Smallest."); else if(pivotIndex > (low + (k-1))){ int[] a2 = new int[pivotIndex-1]; //create a subarray for smaller comparables for(int x = 0; x <=pivotIndex; x++){ a2[x] = array[x]; } count += quickSelect(a2, 0, a2.length-1, k); } else{ int[] a3 = new int[array.length - (pivotIndex+1)]; //create a subarray for larger comparables for(int y = 0; y < a3.length; y++){ a3[y] = array[y]; } count += quickSelect(a3, 0, a3.length, k); } //j++; //System.out.println(j);   return count; }   static int swap(int[] array, int i, int j, int pivotIndex) { int temp = array[i];   array[i] = array[j]; array[j] = temp;   return pivotIndex; } }```

The code works fine up until the if statements which compare the pivot position (pivotIndex) to k. It's here where I'm getting the error. I'm not exactly sure how I'm going outside of the array or if I completely botched this part of the code. Any hints?
• April 12th, 2013, 10:31 AM
Norm
Re: QuickSelect Help
Quote:

java.lang.ArrayIndexOutOfBoundsException error
Check the code to see why the index goes out of bounds.
Remember that array indexes range in value from 0 to the array length-1

Try debugging the code by adding some println statements to print out the values of variables so you can see what the computer is seeing when it executes the code.

Can you post the full text of the error message?
• April 12th, 2013, 05:32 PM
3sbwya
Re: QuickSelect Help
Yeah the error message is:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 13
at qselect.QSelect.quickSelect(QSelect.java:91)
at qselect.QSelect.main(QSelect.java:33)
• April 12th, 2013, 05:57 PM
Norm
Re: QuickSelect Help
Quote:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 13
at qselect.QSelect.quickSelect(QSelect.java:91)
Look at line 91 and find the index that gets the value past the end of the array.
Then check the logic to see how the index got that value.

Use the println() method to print out the values of the indexes if there is more than one.
• April 12th, 2013, 11:22 PM
3sbwya
Re: QuickSelect Help
Ok thanks! I think I got it.