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

Question

i have done following code from programming 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

which is line 21? which is line 36? why is your code formatted so badly? why are there no comments? i can't even be bothered to read this. — fearofawhackplanet, Jun 05 '10 at 10:33
Help what? Explain how the algorithm works in general terms? Tell you why your code isn't working? Provide a fix? Show you a better / more idiomatic method? All of the above? — Mark Byers, Jun 05 '10 at 10:34
here is mistakes which is written in color sentences help to fix these mistakes — , Jun 05 '10 at 10:37
You aren't making it easy for people to help you. Some suggestions: mark lines 21/36, include the pseudocode/tell where you found the pseudocode (page number), and indent the code correctly. — rettvest, Jun 05 '10 at 12:03
I will be sending [multilanguage SO](http://stackoverflow.com/users/20654/support-multilanguage-so) a check...a just need an address. — Rusty, Jun 05 '10 at 12:20

score 4 · Answer 1 · answered Jun 05 '10 at 11:24

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.

Rusty nice story but here i dont understand why talk it if want help or please — , Jun 05 '10 at 11:28

score 3 · Answer 2 · edited May 23 '17 at 12:25

3

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:

Wikipedia link:

Selection algorithm

edited May 23 '17 at 12:25

Community

1
1

answered Jun 05 '10 at 10:36

Mark Byers

811,555
193
1,581
1,452

i have changed it as int c=x[i]; x[i]=x[j]; x[j]=c – Jun 05 '10 at 10:45
but no effects mistake is this Exception in thread "main" java.lang.IllegalArgumentException: n must be positive – Jun 05 '10 at 10:46

score 2 · Answer 3 · answered Jun 05 '10 at 12:32

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.

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

3 Answers3