Hi I have implemented a random selection function to find the order statistic and I am experiencing some overflow even when my pivot element value is within range of the Array. Can some one please point out what is wrong with my computation of the pivot element? I have modified my computation of the pivot element from that used in the R-Quicksort. I have included the code below:
//
// RandomSelection.cpp
//
// Random selection will find the ith smallest ellement or
//
#include <iostream>
#include <stdlib.h>
#include <ctime>
using namespace std;
void swap( int* a, int* b){
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int partition(int Array[],int low,int high){
int Size = high +1;
if(Size<2){
return 0;
}
else {
int i = low;
int j = high;
int pivot_index = low + (rand()%(high-low + 1));
cout <<"pivot_index = "<< pivot_index<< endl;
int pivot = Array[ pivot_index]; //randomly chosing pivot value.
cout<<"pivot value is equal to "<<pivot<<endl;
while (i <= j){
while( Array[i] < pivot){
i++;
}
while(Array[j]> pivot){
j--;
}
if( i<=j){
swap(Array[i],Array[j]);
i++;
j++;
}
}
return i;
}
}
int R_Select(int Array[], int low, int high, int nth_smallest){
cout<<"n th smallest "<<nth_smallest <<endl;
int q = partition(Array,0, high);
cout<<"q = "<<q<<endl;
int k= q -low +1;
cout<<"k = "<<k<<endl;
if(nth_smallest == k){
return Array[q];
}
if(nth_smallest< k){
cout<<"low = "<<low<<endl;
return R_Select(Array,low, q-1, nth_smallest);
}
else{
cout<<"low2 = "<<low<<endl;
return R_Select(&Array[q],q+1,high,nth_smallest-k);
}
}
int main(void){
int const iSize = 10;
int iArray[iSize] ={4,12,15,0,5,3,2,1,9,10};
int ismallest=6;
int ihigh = iSize - 1;
int s;
int ilow=0;
srand((unsigned int) time(0));
//cout<<"Please enter in an order statistic:";
//cin>>ismallest;
s = R_Select(iArray,ilow,ihigh,ismallest);
cout<<"The ith smallest "<<ismallest<< " element of the array is "<< s
<<endl;
return 0;
}
Aucun commentaire:
Enregistrer un commentaire