Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: QuickSelect Help

  1. #1
    Junior Member
    Join Date
    Feb 2013
    Posts
    11
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default QuickSelect Help

    I'm work on the quickSelect algorithm to find the kth smallest integer however I keep getting the java.lang.ArrayIndexOutOfBoundsException error.

    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?

  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: QuickSelect Help

    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?
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Feb 2013
    Posts
    11
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default 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)

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: QuickSelect Help

    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.
    If you don't understand my answer, don't ignore it, ask a question.

  5. The Following User Says Thank You to Norm For This Useful Post:

    3sbwya (April 12th, 2013)

  6. #5
    Junior Member
    Join Date
    Feb 2013
    Posts
    11
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: QuickSelect Help

    Ok thanks! I think I got it.