quick select is not working for all indexes

Question

I am trying to implement quick select referring to a algorithm given in the following link http://www.cs.yale.edu/homes/aspnes/pinewiki/QuickSelect.html

But the program crashes for many k values, and works fine for only few. Kindly guide me where i am doing wrong.

#include <stdio.h>
#include <stdlib.h>

int a1[10];
int a2[10];

int quickselect(int a[], int k,int len){
        int r = rand()%(len-1);

        int pivot = a[r];
        int i =0;
        int len1=0,len2=0;
        for(i=0 ;i<len;i++){
        if(a[i]<pivot)
            a1[len1++]=a[i];
        else if(a[i]>pivot)
            a2[len2++] = a[i];
        else
            continue;
    }

    if(k<=len1)
        return quickselect(a1, k,len1);
    else if (k > len-len2)
        return quickselect(a2, k - (len-len2),len2);

    return pivot;

}
int main()
{
  int a[7] = {8,3,2,6,1,9,5};
  int val = quickselect(a,3,7);
  printf("%d \n",val);

  return 0;
}

Answer 1

I have test your code. I think you should change int r = rand()%(len-1) to int r = rand()%len because when len==1you will get a floating point exception.