CODEWITHSUNDEEP
c++calgorithm
Mushahid Hussain
Mushahid Hussain

Reputation: 4045

order statistic implmentation

hey everybody i am trying to implement code for finding order statistic but i am getting a error ..in algorithm two variables are passed in random function is there any way to pass two variables in it if yes than how?? and if no then what can be its alternate ... your help will be appreciated

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>

int RandomizedSelect(int*,int,int,int);
int RandomizedPartition(int*, int, int);
int partion(int*,int,int);
void main()
{
    int n,x,i;
    cout<<"Enter length of array";
    cin>>n;
    int *a=new int[n];
    cout<<"Enter elements of array";
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cout<<"Enter element less than size of array";
    cin>>x;
    int z=RandomizedSelect(a,0, n, x);
    cout<<z;
    getch();


}

int RandomizedSelect(int A[],int p, int r,int i)
{
    if (p == r)
    {
        return A[p];
    }
    int q = RandomizedPartition(A, p, r);
    int k = q - p + 1;
    if (i == k)
    {
        return A[q];
    }
    else if  (i < k)
    {
        return RandomizedSelect(A, p, q-1, i) ;
    }
    else return RandomizedSelect(A, q+1, r, i - k);
 }
int Partition(int A[],int p,int r)
{
    int x=A[r],temp;
    int i=p-1,j;
    for(j=p;j<r-1;j++)
    {
        if(A[j]<=x)
        {
            i++;
            temp=A[i];
            A[i]=A[j];
            A[j]=temp;
        }
    }
    temp=A[i+1];
    A[i+1]=A[r];
    A[r]=temp;
    return i+1;

}
int RandomizedPartition(int A[],int p,int r)
{

 int temp;
 int j = random(p,r);
 temp=A[r];
 A[r]=A[j];
 A[j]=temp;
 return Partition(A, p, r);
}

Upvotes: 0

Views: 1605

Answers (2)

Puneet Gupta
Puneet Gupta

Reputation: 21

Above code is not working in some case.Here is the corrected code. Below code is working properly I have checked for all cases.

#include<iostream>
#include<cstdlib>
using namespace std;

int RandomizedSelect(int*,int,int,int);
int RandomizedPartition(int*, int, int);
int partion(int*,int,int);
int main()
{
int n,x,i;
cout<<"Enter length of array: ";
cin>>n;
int *a=new int[n];
cout<<"Enter elements of array: ";
for(i=0;i<n;i++)
{
    cin>>a[i];
}
cout<<"Enter element less than size of array: ";
cin>>x;
int z=RandomizedSelect(a,0, n-1, x);
cout<<z;
}

int RandomizedSelect(int A[],int p, int r,int i)
{
if (p == r)
{
    return A[p];
}
int q = RandomizedPartition(A, p, r);
int k = q - p + 1;
if (i == k)
{
    return A[q];
}
else if  (i < k)
{
    return RandomizedSelect(A, p, q-1, i) ;
}
    else return RandomizedSelect(A, q+1, r, i - k);
 }
int Partition(int A[],int p,int r)
{
int x=A[r],temp;
int i=p-1,j;
for(j=p;j<r;j++)
{
    if(A[j]<=x)
    {
        i++;
        temp=A[i];
        A[i]=A[j];
        A[j]=temp;
    }
}
temp=A[i+1];
A[i+1]=A[r];
A[r]=temp;
return i+1;

}
int RandomizedPartition(int A[],int p,int r)
{

 int temp;
 int j = p + rand()%(r-p+1);
 temp=A[r];
 A[r]=A[j];
 A[j]=temp;

 return Partition(A, p, r);
}

Upvotes: 2

Alexey Kukanov
Alexey Kukanov

Reputation: 12784

To select a random value between p and r, you may use this formula:

p + rand()%(r-p+1);

rand() gives you a pseudo-random integer value in [0, RAND_MAX]. Then you take the remainder (%), thus converting to a value in [0, r-p] (as long as r-p+1 is less than RAND_MAX). Adding it to p, you get a value in [p, r].

Upvotes: 1

Related Questions