split up array
how do i partition array 1000002 elements into elements/n +elements%n
what kind of array
static int[n];
static int* arr=new int[n]
i am trying to implement worst linear select algorithm but can't seem to go above 150 elements.
[269 byte] By [
whatnow] at [2007-11-20 11:03:22]

# 3 Re: split up array
I been staring at this code for a day now i can't get it to work pass 150 elements
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<fstream>
using namespace std;
#define element 100
int selectworstcase(int [],int,int);
int sort(int [],int,int);
int main()
{
srand((time(0)));
static int test[element];
for(int i=0;i<element;i++)
{
test[i]=rand()%20;
}
sort(test,element,0);
cout<<"what ith number do you want"<<endl;
int e;
cin>>e;
clock_t start2=clock();
int i=selectworstcase(test,element,e);
clock_t stop2=clock();
cout<<"answer "<<i<<" answer"<<endl;
double totaltime2=double(stop2-start2)/CLOCKS_PER_SEC;
cout<<"worst case took"<<totaltime2<<endl;
return 0;
}
int selectworstcase(int a[],int size,int ith)
{
if(size<=10)
{
return sort(a,size,ith);
}
static int less[element];
static int greater[element];
int lcount=0,ecount=0,gcount=0;
int pivot;
static int* median;
median=new int[(size/5)+(size%5)];
static int temp[5];
int counter=0;
for(int i=0;i<(size/5);i++)
{
for(int j=0;j<5;j++,counter++)
{
temp[j]=a[counter];
}
median[i]=selectworstcase(temp,5,3);
}
if(size%5>0)
{
for(int i=0;i<(size%5);i++,counter++)
{
temp[i]=a[counter];
}
median[size/5]=selectworstcase(temp,size%5,((size%5)/2)+1);
/*for(int i=0;i<(size/5)+1;i++)
{
cout<<median[i]<<endl;
}*/
pivot=selectworstcase(median,(size/5)+1,(((size/5)+1)/2)+1);
}
else
{
/*for(int i=0;i<(size/5);i++)
{
cout<<median[i]<<endl;
}*/
pivot=selectworstcase(median,(size/5),(((size/5))/2)+1);
}
/*cout<<"PIVOT "<<pivot<<" PIVOT"<<endl;*/
int l=0,g=0;
for(int i=0;i<size;i++)
{
if(a[i]<pivot)
{
less[l]=a[i];
l++;
}
else
{
greater[g]=a[i];
g++;
}
}
if(l>ith)
{
return selectworstcase(less,l,ith);
}
else
if(l<ith)
{
return selectworstcase(greater,g,ith-l);
}
else
return pivot;
}
int sort(int a[],int size,int ith)
{
/*cout<<"Entering sorting"<<endl;*/
int i,j,index;
for(i=0;i<size;i++)
{
index=a[i];
j=i;
while((j>0)&&(a[j-1]>index))
{
a[j]=a[j-1];
j--;
}
a[j]=index;
}
/*cout<<endl;*/
/*for(i=0;i<size;i++)
{
if(i%5==0)
cout<<" ";
cout<<a[i]<<" ";
}*/
/*cout<<endl<<endl;*/
return a[ith-1];
}