#define SWAP( x, y ) { int t=x; x=y; y=t; }
//
void quicksort1( int*A, int beg, int end )
{
int i, j;
int p;
if ( beg >= end )
{
return;
}
i = beg;
j = end+1;
p = A[beg];
for ( ;; )
{
while( ++i <= end && A[i] < p );
while( A[--j] > p );
if ( i > j )
break;
SWAP( A[i], A[j]);
}
SWAP( A[beg], A[j] );
quicksort1( A, beg, j-1 );
quicksort1( A, j+1, end );
}
//
void quicksort2( int* A, int n )
{
struct sbe
{
int beg;
int end;
};
sbe* arr = new sbe[n];
int m;
int p;
int beg, end, i, j;
m = 0;
arr[0].beg = 0;
arr[0].end = n-1;
for ( ; ; )
{
if ( m < 0 )
break;
beg = arr[m].beg;
end = arr[m--].end;
if ( beg >= end )
continue;
// partition
p = A[beg];
i = beg;
j = end+1;
for ( ; ; )
{
while( ++i <= end && A[i] < p ); // ! while( A[++i] < p ); error
while( A[--j] > p );
if ( i > j )
break;
SWAP( A[i], A[j] );
}
SWAP( A[j], A[beg] );
arr[++m].beg = beg;
arr[m].end = j-1;
arr[++m].beg = j+1;
arr[m].end = end;
}
delete [] arr;
}
//
void QuickSort( int* A //
, int n //
, int method // ,0 - , 1 -
)
{
if ( method == 0 )
{
quicksort1( A, 0, n-1 );
}
else
{
quicksort2( A, n );
}
}