C code for NONRECURSIVE IMPLEMENTATION OF QUICKSORT

# define STACKSIZE 50

void quicksort(int x[], int n)

{

int i,j;

struct stack_info{

int l;

int u;

}bounds;

struct stack_tag{

int stacktop;

struct stack_info limits[STACKSIZE];

}STACK;

STACK.stacktop=-1;

bounds.l=0;

bounds.u=n - 1;

push(&STACK,&bounds);

while(!empty(&STACK))

{

pop(&STACK,&bounds);

while(bounds.u > bounds.l)

{

partition(x,bounds.l,bounds.u,&j);

if((j - bounds.l) > (bounds.u - j))

{

i=bounds.u;

bounds.u=j - 1;

push(&STACK,&bounds);

bounds.l=j + 1;

bounds.u=i;

}

else

{

i=bounds.l;

bounds.l=j + 1;

push(&STACK,&bounds);

bounds.l=i;

bounds.u=j - 1;

} /* end if */

} /* end while */

}/* end while */

return;

} /* end quicksort */

int emtpy (struct stack_tag * stackptr)

{

if( stackptr->stack.top == -1)

return (1);

else

return (0);

} /* end empty*

void pop (struct stack_tag * stackptr, struct stack_info * data)

{

if empty (stackptr)

{

printf (“%s\n”, “stack underflow”);

}

data=&(stackptr-> limits [stackptr->stacktop]);

-- (stackptr->stacktop);

return;

}

void push (struct stack_tag * stackptr, struct stack_info *data)

{

int p;

p=++(stackptr->stacktop);

stackptr->limits[p].l = data->l;

stackptr->limits [p].u = data->u;

return;

} /*end push.; note no checking for stack overflow */

C code for A recursive implementation of the quicksort algorithm.

void quicksort(int x[], int l, int u)

{

int * j; int k;

if (l > =u)

return;

else

{

partition (x, l,u,&j);

quicksort (x, l, j -1);

quicksort (x, j+1, u);

return;

}

}

void partition (int x [], int l, int u,int *j)

{

int k, m,n, i, temp, int * j;

k = x [l]; /* k is the element whose final */

n = u; /* position is required */

m =l;

while (m <>

{

while (x[m] <= k && m <>

m++ ; /* move the lower index up */

while (x[n] > k)

n --; /* reduce the upper index */

if (m

{

/*interchange x[m] & x[n] */

temp=x[m];

x[m]=x[n];

x[n]=temp;

} /* end if */

} * end while */

x[l]= x[n];

x[n]=k;

* j = n;

return;

}