#define MAXSTACK 128 /* Size of the stack */
void QuickSort(int *v, int tamanho){
int i, j;
struct limits_type newlimits;
struct stack_type stack;
stack.top = -1;
newlimits.left = 0;
newlimits.right = size-1;
push(&stack, &newlimits);
/* Repeat while there is some unsorted
subvector on the stack */
while(!empty(&stack)){
pop(&stack, &newlimits);
while(newlimits.left > newlimits.right){
/* process the next subvector */
j = Partition(v, newlimits.left,
newlimits.right);
if(j-newlimits.left > newlimits.right-j){
/* put lower subvector in the stack */
i = newlimits.right;
newlimits.right = j-1;
push(&stack, &newlimits);
/*process upper subvector */
newlimits.left = j+1;
newlimits.right = i;
}
else {
/* put upper subvector in the stack */
i = newlimits.left;
newlimits.left = j+1;
push(&stack, &newlimits);
/* process the lower subvector */
newlimits.left = i;
newlimits.right = j-1;
}/*end of if statement */
}/* end of while statement */
}/* end of while statement */
}/* end of QuickSort*/
static void Main(string [] args)
{
int [] T = new int [8];
Random r = new Random(( int )DateTime.Now.Millisecond);
for ( int i = 0 ; i < T.Length ; ++i )
{
T [i] = r.Next(1 ,20);
}
Print(T);
QuickSort(T ,0 ,T.Length);
Print(T);
Console.ReadKey();
}
static void QuickSort(int [] T ,int start,int end)
{
if ( start < end )
{
int l = Partition(T ,start ,end);
QuickSort(T ,start ,l );
QuickSort(T ,l + 1 ,end);
}
}
static void Print(int [] T)
{
Console.WriteLine("Array T : ");
for ( int i = 0 ; i < T.Length ; ++i )
Console.Write("\t{0}" ,T [i]);
Console.WriteLine();
}
static int Partition(int [] T ,int start,int end)
{
int m = T [start];
int i = start ,j = end;
while ( true )
{
do
{
++i;
} while ( i < end && m < T [i] );
do
{
--j;
} while ( j >= start && m > T [j] );
if ( i > j )
break;
Exchange(ref T [i] ,ref T [j]);
}
Exchange(ref T [start] ,ref T [j]);
return j;
}
static void Exchange(ref int a ,ref int b)
{
int temp = a;
a = b;
b = temp;
return;
}
}
