#include <iostream>
using namespace std;
int numswap = 0 ;
void swap( int a[ ] , int i, int j)
{
int tmp = a[ i] ; a[ i] = a[ j] ; a[ j] = tmp;
numswap++ ;
}
void minHeapify( int a[ ] , int s, int elem)
{
int left = 2 * elem + 1 ;
int right = 2 * elem + 2 ;
int smallest = elem;
if ( left < s && a[ smallest] > a[ left] )
smallest = left;
if ( right < s && a[ smallest] > a[ right] )
smallest = right;
if ( smallest ! = elem)
{
swap( a,smallest,elem) ;
minHeapify( a,s,smallest) ;
}
}
void buildHeap( int a[ ] , int s)
{
for ( int i = s/ 2 ; i >= 0 ; -- i)
minHeapify( a,s,i) ;
}
void heapSort( int a[ ] , int s)
{
buildHeap( a,s) ;
for ( int i= s- 1 ; i>= 1 ; -- i)
{
swap( a,0 ,i) ;
minHeapify( a,i,0 ) ;
}
}
const int SIZE = 1000000 ;
int a[ SIZE+ 1 ] ;
void generate( )
{
numswap = 0 ;
for ( int i= 0 ; i<= SIZE; ++ i)
a[ i] = rand ( ) % 3000 ;
}
void verify( int s)
{
for ( int i= 1 ; i< s; ++ i)
if ( a[ i- 1 ] < a[ i] ) { printf ( "Invalid sort" ) ; exit ( - 1 ) ; }
}
int main( ) {
for ( int i= 10 ; i<= SIZE; i* = 10 )
{
generate( ) ;
heapSort( a,i) ;
//for (int j=0; j<i; ++j)
//printf("%i ", a[j]);
//printf("\n");
verify( i) ;
printf ( "Sorting %8i elements in %8i swaps\n " , i, numswap) ;
}
return 0 ;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG51bXN3YXAgPSAwOwp2b2lkIHN3YXAoaW50IGFbXSwgaW50IGksIGludCBqKQp7CglpbnQgdG1wID0gYVtpXTsgYVtpXSA9IGFbal07IGFbal0gPSB0bXA7CgludW1zd2FwKys7Cn0KCnZvaWQgbWluSGVhcGlmeShpbnQgYVtdLCBpbnQgcywgaW50IGVsZW0pCnsKCWludCBsZWZ0ID0gMiplbGVtICsgMTsKCWludCByaWdodCA9IDIqZWxlbSArIDI7CglpbnQgc21hbGxlc3QgPSBlbGVtOwoJaWYgKGxlZnQgPCBzICYmIGFbc21hbGxlc3RdID4gYVtsZWZ0XSkKCQlzbWFsbGVzdCA9IGxlZnQ7CglpZiAocmlnaHQgPCBzICYmIGFbc21hbGxlc3RdID4gYVtyaWdodF0pCgkJc21hbGxlc3QgPSByaWdodDsKCWlmIChzbWFsbGVzdCAhPSBlbGVtKQoJewoJCXN3YXAoYSxzbWFsbGVzdCxlbGVtKTsKCQltaW5IZWFwaWZ5KGEscyxzbWFsbGVzdCk7Cgl9Cn0KCnZvaWQgYnVpbGRIZWFwKGludCBhW10sIGludCBzKQp7Cglmb3IgKGludCBpID0gcy8yOyBpID49IDA7IC0taSkKCQltaW5IZWFwaWZ5KGEscyxpKTsKfQoKdm9pZCBoZWFwU29ydChpbnQgYVtdLCBpbnQgcykKewoJYnVpbGRIZWFwKGEscyk7Cglmb3IgKGludCBpPXMtMTsgaT49MTsgLS1pKQoJewoJCXN3YXAoYSwwLGkpOwoJCW1pbkhlYXBpZnkoYSxpLDApOwoJfQp9Cgpjb25zdCBpbnQgU0laRSA9IDEwMDAwMDA7CmludCBhW1NJWkUrMV07CnZvaWQgZ2VuZXJhdGUoKQp7CgludW1zd2FwID0gMDsKCWZvciAoaW50IGk9MDsgaTw9U0laRTsgKytpKQoJCWFbaV0gPSByYW5kKCkgJSAzMDAwOwp9Cgp2b2lkIHZlcmlmeShpbnQgcykKewoJZm9yIChpbnQgaT0xOyBpPHM7ICsraSkKCQlpZiAoYVtpLTFdIDwgYVtpXSkgeyBwcmludGYoIkludmFsaWQgc29ydCIpOyBleGl0KC0xKTsgfQp9CgppbnQgbWFpbigpIHsKCQoJZm9yIChpbnQgaT0xMDsgaTw9U0laRTsgaSo9MTApCgl7CgkJZ2VuZXJhdGUoKTsKCQloZWFwU29ydChhLGkpOwoJCS8vZm9yIChpbnQgaj0wOyBqPGk7ICsraikKCQkJLy9wcmludGYoIiVpICIsIGFbal0pOwoJCS8vcHJpbnRmKCJcbiIpOwoJCXZlcmlmeShpKTsKCQlwcmludGYoIlNvcnRpbmcgJThpIGVsZW1lbnRzIGluICU4aSBzd2Fwc1xuIiwgaSwgbnVtc3dhcCk7Cgl9CgkKCXJldHVybiAwOwp9