Cod sursa(job #549405)
#include <ctime>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 500011
using namespace std;
int N;
int v[N_MAX];
inline void _swap( int& x, int& y ) { int aux=x; x=y; y=aux; }
inline int MedianOf3( int x, int y, int z )
{
int w[]={ x, y, z };
for( int i=0; i < 2; ++i )
for( int j=i+1; j < 3; ++j )
if( v[w[i]] > v[w[j]] )
_swap( w[i], w[j] );
return w[1];
}
inline void QSort( int left, int right )
{
if( left < right )
{
_swap( v[rand()%(right-left+1)+left], v[(right+left)/2] );
int xIndex=MedianOf3( left, (right+left)/2, right ), xLeft, xRight;
for( xLeft=left-1, xRight=right+1; ; )
{
for( ++xLeft; xLeft <= right && v[xIndex] > v[xLeft]; ++xLeft );
for( --xRight; xRight >= left && v[xIndex] < v[xRight]; --xRight );
if( xLeft > xRight )
break;
_swap( v[xLeft], v[xRight] );
}
if( xLeft < right )
QSort( xLeft, right );
if( xRight > left )
QSort( left, xRight );
}
}
int main( void )
{
srand( time(NULL) );
ifstream in( "algsort.in" );
in>>N;
copy( istream_iterator<int>(in), istream_iterator<int>(), v+1 );
QSort( 1, N );
ofstream out( "algsort.out" );
copy( v+1, v+N+1, ostream_iterator<int>( out, " " ) );
out<<'\n';
return EXIT_SUCCESS;
}