Cod sursa(job #549405)

Utilizator BitOneSAlexandru BitOne Data 8 martie 2011 16:10:12
Problema Sortare prin comparare Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#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;
}