#include <iostream>
#include <time.h>
using namespace std;
#define min(a,b) ((a) < (b) ? (a) : (b))
int numswaps = 0 ;
void swap( int a[ ] , int i, int j)
{
int tmp = a[ i] ; a[ i] = a[ j] ; a[ j] = tmp;
numswaps++ ;
}
int select( int a[ ] , int k, int l, int r) ;
void printArr( int a[ ] , int l, int r)
{
for ( int i= l; i<= r; ++ i)
printf ( "%i " , a[ i] ) ;
printf ( "\n " ) ;
}
void insertSort( int a[ ] , int l, int r)
{
for ( int i= l+ 1 ; i<= r; ++ i)
{
int j = i;
while ( j> l && a[ j] < a[ j- 1 ] )
{
swap( a,j,j- 1 ) ;
j-- ;
}
}
}
int medMed( int a[ ] , int l, int r)
{
int j = l- 1 ;
for ( int i= l; i<= r; i+ = 5 )
{
int rr = min( i+ 4 ,r) ;
insertSort( a,i,rr) ;
swap( a,++ j,( i+ rr) / 2 ) ;
}
int m = ( j- l) / 2 + 1 ;
return select( a,m,l,j) ;
}
int partition( int a[ ] , int l, int r)
{
int pp = medMed( a,l,r) ;
swap( a[ pp] ,a[ r] ) ;
int p = a[ r] ;
int i = l- 1 ;
for ( int j= l; j< r; ++ j)
if ( a[ j] < p)
swap( a,++ i,j) ;
swap( a,++ i,r) ;
return i;
}
int numselect = 0 ;
int select( int a[ ] , int k, int l, int r)
{
numselect++ ;
if ( l> r) { printf ( "error l>r\n " ) ; exit ( - 1 ) ; }
if ( l== r) { if ( k == 1 ) return l; printf ( "error k!=1" ) ; exit ( - 1 ) ; }
int p = partition( a,l,r) ;
if ( k< p+ 1 - l) select( a,k,l,p- 1 ) ;
else if ( k> p+ 1 - l) select( a,k- ( p+ 1 - l) ,p+ 1 ,r) ;
else return p;
}
const int SIZE = 10000000 ;
int arr[ SIZE+ 1 ] ;
void generate( )
{
numswaps = 0 ;
numselect = 0 ;
for ( int i= 0 ; i<= SIZE; ++ i)
arr[ i] = rand ( ) ;
}
void verify( int s)
{
int last = - 1 ;
for ( int i= 1 ; i<= s; ++ i)
{
int cur = select( arr,i,0 ,s) ;
if ( last > cur) { printf ( "invalid" ) ; exit ( - 2 ) ; }
last = cur;
}
}
int main( ) {
clock_t begin = clock ( ) ;
for ( int i= 1 ; i<= SIZE; i* = 10 )
{
generate( ) ;
select( arr,( 1 + i) / 2 ,1 ,i) ;
printf ( "#swaps for finding median of %8i elements: %8i (%i)\n " , i, numswaps, numselect) ;
}
clock_t end = clock ( ) ;
double time = ( double ) ( end - begin) / CLOCKS_PER_SEC ;
printf ( "Total time: %f" , time ) ;
return 0 ;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dGltZS5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBtaW4oYSxiKSAoKGEpIDwgKGIpID8gKGEpIDogKGIpKQoKaW50IG51bXN3YXBzID0gMDsKdm9pZCBzd2FwKGludCBhW10sIGludCBpLCBpbnQgaikKewoJaW50IHRtcCA9IGFbaV07IGFbaV0gPSBhW2pdOyBhW2pdID0gdG1wOwoJbnVtc3dhcHMrKzsKfQoKaW50IHNlbGVjdChpbnQgYVtdLCBpbnQgaywgaW50IGwsIGludCByKTsKdm9pZCBwcmludEFycihpbnQgYVtdLCBpbnQgbCwgaW50IHIpCnsKCWZvciAoaW50IGk9bDsgaTw9cjsgKytpKQoJCXByaW50ZigiJWkgIiwgYVtpXSk7CglwcmludGYoIlxuIik7Cn0KCnZvaWQgaW5zZXJ0U29ydChpbnQgYVtdLCBpbnQgbCwgaW50IHIpCnsKCWZvciAoaW50IGk9bCsxOyBpPD1yOyArK2kpCgl7CgkJaW50IGogPSBpOwoJCXdoaWxlIChqPmwgJiYgYVtqXSA8IGFbai0xXSkKCQl7CgkJCXN3YXAoYSxqLGotMSk7CgkJCWotLTsKCQl9Cgl9Cn0KCmludCBtZWRNZWQoaW50IGFbXSwgaW50IGwsIGludCByKQp7CglpbnQgaiA9IGwtMTsKCWZvciAoaW50IGk9bDsgaTw9cjsgaSs9NSkKCXsKCQlpbnQgcnIgPSBtaW4oaSs0LHIpOwoJCWluc2VydFNvcnQoYSxpLHJyKTsKCQlzd2FwKGEsKytqLChpK3JyKS8yKTsKCX0KCWludCBtID0gKGotbCkvMisxOwoJcmV0dXJuIHNlbGVjdChhLG0sbCxqKTsKfQoKaW50IHBhcnRpdGlvbihpbnQgYVtdLCBpbnQgbCwgaW50IHIpCnsKCWludCBwcCA9IG1lZE1lZChhLGwscik7Cglzd2FwKGFbcHBdLGFbcl0pOwoJaW50IHAgPSBhW3JdOwoJaW50IGkgPSBsLTE7Cglmb3IgKGludCBqPWw7IGo8cjsgKytqKQoJCWlmIChhW2pdIDwgcCkKCQkJc3dhcChhLCsraSxqKTsKCXN3YXAoYSwrK2kscik7CglyZXR1cm4gaTsKfQoKaW50IG51bXNlbGVjdCA9IDA7CmludCBzZWxlY3QoaW50IGFbXSwgaW50IGssIGludCBsLCBpbnQgcikKewoJbnVtc2VsZWN0Kys7CglpZiAobD5yKSB7IHByaW50ZigiZXJyb3IgbD5yXG4iKTsgZXhpdCgtMSk7IH0KCWlmIChsPT1yKSB7IGlmIChrID09IDEpIHJldHVybiBsOyBwcmludGYoImVycm9yIGshPTEiKTsgZXhpdCgtMSk7IH0KCWludCBwID0gcGFydGl0aW9uKGEsbCxyKTsKCWlmIChrPHArMS1sKSBzZWxlY3QoYSxrLGwscC0xKTsKCWVsc2UgaWYgKGs+cCsxLWwpIHNlbGVjdChhLGstKHArMS1sKSxwKzEscik7CgllbHNlIHJldHVybiBwOwp9Cgpjb25zdCBpbnQgU0laRSA9IDEwMDAwMDAwOwppbnQgYXJyW1NJWkUrMV07CnZvaWQgIGdlbmVyYXRlKCkKewoJbnVtc3dhcHMgPSAwOwoJbnVtc2VsZWN0ID0gMDsKCWZvciAoaW50IGk9MDsgaTw9U0laRTsgKytpKQoJCWFycltpXSA9IHJhbmQoKTsKfQp2b2lkIHZlcmlmeShpbnQgcykKewoJaW50IGxhc3QgPSAtMTsKCWZvciAoaW50IGk9MTsgaTw9czsgKytpKQoJewoJCWludCBjdXIgPSBzZWxlY3QoYXJyLGksMCxzKTsKCQlpZiAobGFzdCA+IGN1cikgeyBwcmludGYoImludmFsaWQiKTsgZXhpdCgtMik7IH0KCQlsYXN0ID0gY3VyOwoJfQp9CmludCBtYWluKCkgewoJY2xvY2tfdCBiZWdpbiA9IGNsb2NrKCk7Cglmb3IgKGludCBpPTE7IGk8PVNJWkU7IGkqPTEwKQoJewoJCWdlbmVyYXRlKCk7CgkJc2VsZWN0KGFyciwoMStpKS8yLDEsaSk7CgkJcHJpbnRmKCIjc3dhcHMgZm9yIGZpbmRpbmcgbWVkaWFuIG9mICU4aSBlbGVtZW50czogJThpICglaSlcbiIsIGksIG51bXN3YXBzLCBudW1zZWxlY3QpOwoJfQoJY2xvY2tfdCBlbmQgPSBjbG9jaygpOwoJZG91YmxlIHRpbWUgPSAoZG91YmxlKShlbmQgLSBiZWdpbikgLyBDTE9DS1NfUEVSX1NFQzsKCXByaW50ZigiVG90YWwgdGltZTogJWYiLCB0aW1lKTsKCXJldHVybiAwOwp9