select k th mimimum from array a[0..n-1]

Question

i have done folloing code from progrmming pearls here is code

import java.util.*;
public class select {
public static int select1(int x[],int l,int u,int k){
    //pre l<=k<=u
    //post x[l..k-1]<=x[k]<=x[k+1..u]
    Random r=new Random();
   int  t=r.nextInt(u-1-l)+l;
     if (l>=u) return -1 ;
    swap(l,t);
    int s=x[l];
    int i=l;
     int j=u+1;
       while (true){
         do
         {
              i++;
         }while (i<=u && x[i]<t);
         do
         {
              j--;
         }while (x[j]>t);
          if (i>j)  break;
           int temp=x[i]; x[i]=x[j];x[j]=t;
            swap(l,j);

             if (j<k){
               return   select1(x,j+1,u,k);

         }
       }
            return    select1(x,l,j-1,k);
           }

    public static void main(String[] args) {
        int x[]=new int[]{4,7,9,3,2,12,13,10,20};
                  select1(x,0,x.length-1,5);

    }



    public static void swap(int i,int j){
        int c=i;
        i=j;
        j=c;



    }
}

but here is mistake

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
        at select.select1(select.java:21)
        at select.main(select.java:36)
Java Result: 1

please help

Answer 1

One of the problems with your code is this:

public static void swap(int i, int j)
{
    int c=i;
    i=j;
    j=c;
}

This function doesn't do anything. Java uses pass-by-value so the original variables are unaffected.

By the way, there are already other questions that cover the topic of finding the kth largest/smallest value in an unsorted array in a variety of languages:

• How to find the kth largest element in an unsorted array of length n in O(n)?
• Finding Nth item of unsorted list without sorting the list

Wikipedia link:

• Selection algorithm

Answer 2

Do it by hand...step by step...write down on a piece of paper. Use a pencil and a calculator. You will find the error and you might learn something along the way...maybe.

[Warning: Story coming]

Let me tell you a little story about a man that was first in his family to go to college...

My father was a young engineer in the mid 1960s. He work for NASA's Apollo project. Specifically as as specialist working on the Lunar Accent rocket motors. He wrote software that simulated motor performance over the expected burn. Normal and abnormal events could then be modeled and validated against flight hardware. He wrote the code in Fortran...sent it over to the room full of very nice ladies that would generate the punch card stack for him. That stack would then be dropped off at a counter and scheduled for a run. The results came on a ~200 page stack of 11 x 17 tractor feed paper.

With these results my father would retire to one of the small work rooms that surrounded the job printers. He would then test the results manually, going the code by hand validating each step. He had a yellow pad, a bucket of pencils and a slide rule. If it did not validate it would corrected and run again and again...until it was right.

Those motors worked every time and every man came home.

Ok..story over...now:

Grow up, Suck it up and DO SOME WORK. Stop wasting our time.

Answer 3

I don't know what is the main problem but some problems are:

• Variable names are important: what is s, j, i, t... ? If the code is clear, errors are clear.
• Personally, i hate while(true)...break; you can code better than that. Why not try?

Then, as Rusty sad, do some work. Take a pad, a pencil and 5 minutes. Try to simulate. Try to get the error. Try with smaller array. Try. As Feynman sad "What I cannot create, I do not understand." Try to understand your code.