#include<io.h>
#include<stdio.h>
#include "iostream.h"
#include<stdlib.h>
#include<malloc.h>
#include "math.h"
//////////////////////////////////////////////////////////////
void insertion_sort( double* array, int n );
int partition_array( double* array, int n, double pivot )
{
double temp;
int p, i, j;
i = -1;
for( j = 0; j < n; j++ )
if( array[j] <= pivot )
{
temp = array[++i];
array[i] = array[j];
array[j] = temp ;
if( array[i] == pivot )
p = i;
}
array[p] = array[i];
array[i] = pivot;
return i;
}
double rank_select( double* array, int n, int r )
{
double* temp;
double med;
int gr_5, gr_tot, rem_elts, i, j;
/* base case */
if( n == 1 )
return array[0];
/* divide array into groups of 5 and sort them */
gr_5 = n / 5;
gr_tot = ceil( n / 5.0 );
rem_elts = n % 5;
temp = array;
for( i = 0; i < gr_5; i++ )
{
insertion_sort( temp, 5 );
temp += 5;
}
insertion_sort( temp, rem_elts );
/* recursively find the median of the medians of the groups of 5 */
temp = (double *)calloc( gr_tot, sizeof( double ) );
for( i = 0, j = 2; i < gr_5; i++, j += 5 )
temp[i] = array[j];
if( rem_elts )
temp[i++] = array[n - 1 - rem_elts/2];
med = rank_select( temp, i, ( i - 1 ) / 2 );
free( temp);
/* partition around median of medians and recursively select if necessary */
j = partition_array( array, n, med );
if( r == j )
return med;
else if( r < j )
return rank_select( array, j, r );
else
{
array += j+1;
return rank_select( array, ( n - j - 1 ), ( r - j - 1 ) );
}
}
////////////////////////////////////////////////////////////////
void insertion_sort( double* array, int n )
{
double k;
int i, j;
for( i = 1; i < n; i++ )
{
k = array[i];
j = i-1;
while( j >= 0 && array[j] > k )
{
array[j+1] = array[j];
j -= 1;
}
array[j+1] = k;
}
}
void main()
{
double array[]={1,2,7,4,6,9,10,8,0};
int len= sizeof(array)/sizeof(double);
insertion_sort(array,len);
cout<<"sort array is:"<<endl;
for(int i=0;i<len;i++)
{
cout<<array[i]<<"\t";
}
cout<<endl;
cout<<"rank 5 is:"<<rank_select(array,len,5)<<endl;
}
评论0
最新资源