Random Selection -i'th order statistic

Question

The random selection program below doesn't find the i'th order statistic. The following program follows the algorithm provided in Cormen's Introduction to Algorithm. Thanks in advance for finding the bug.

#include<stdio.h>
#include<stdlib.h>
int random(int a,int b) //generates random numbers [a,b]
{
    return a+(rand()%(b-a+1));
}
void swap(int *a,int *b) //swwaps the elements
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}
int partition(int a[],int p,int r) //partitioning similar to that of quicksort
{
    int i=p-1,j,x=a[r];
    for(j=p;j<r;j++)
    {
        if(a[i]<x)
        {
            i++;
            swap(&a[i],&a[j]);
        }
    }
    swap(&a[i+1],&a[r]);
    return i+1;
}
int random_partition(int a[],int p,int r) //random index generation whose element gets swapped with the last element of the array
{
    int q=random(p,r);
    swap(&a[q],&a[r]);
    return partition(a,p,r);
}
int random_selection(int a[],int p,int r,int index) //finds the i'th order statistic
{
    if(p==r)
    return a[p];
    if(p<r)
    {
        int mid,k;
        mid=random_partition(a,p,r);
        k=mid-p+1;
        if(k==index)
        return a[mid];
        if(index<k)
        return random_selection(a,p,mid-1,index);
        if(index>k)
        return random_selection(a,mid+1,r,index);
    }
}
main()
{
    int a[50],i,size,index;
    printf("enter the size of the array\n");
    scanf("%d",&size);
    printf("enter the array elements\n"); //takes array elements input
    for(i=1;i<=size;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=1;i<=size;i++) //prints the index of each element
    {
    printf("%d\n",random_selection(a,1,size,i));
}
}

I have never understood the purpose of srand. Can you please explain? — Koosh Doctor, Jun 19 '15 at 15:10
sorry I was offline and I couldnt reply. Hope you understood the purpose of srand and the seed. — Sourav Kanta, Jun 19 '15 at 15:20
I added srand as suggested. yet for an input of 4 numbers such as 1,4,3,2 and 2 as the index number, I am getting a different ouput every time instead of giving 2 as the 2nd order statistic — Koosh Doctor, Jun 20 '15 at 06:24
also in the partition function, I did a mistake and changed it to if(a[j]<=x), but still i am not getting the desired result. — Koosh Doctor, Jun 20 '15 at 06:37

score 0 · Answer 1 · edited May 23 '17 at 12:14

Do you need a srand() in your main()? Just like these threads Recommended way to initialize srand? and How does srand relate to rand function?

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

int main()
{
   int i, n;
   time_t t;

   n = 5;

   /* Intializes random number generator */
   srand((unsigned) time(&t));

   /* Print 5 random numbers from 0 to 50 */
   for( i = 0 ; i < n ; i++ ) 
   {
      printf("%d\n", rand() % 50);
   }

   return(0);
}

Random Selection -i'th order statistic

1 Answers1