QUICKSORT ALGORITHM

The recursive implementation of quicksort algorithm of an array x of n elements involves initial partitioning of the elements into two halves and followed by the recursive invocation of quicksort function once for each half.

The partitioning algorithm works as follows :

Two integer variables l and u are used to locate the leftmost and the rightmost element of the array x under consideration. While the partitioning algorithm will work with any element of the array selected as pivot (element around which partitioning is done) for comparison, in the following example, we have chosen the leftmost element of the array to be the pivot for the sake of simplicity. In the implementation of the quicksort shown in example 19.1, the pivot is stored in the variable k. Initially the variable m is set to the leftmost element of the array. The elements of the array indexed by m i.e. x[m] is successively compared with the pivot element till an element is found which is larger than the pivot (the variable k of the function partition in example 19.1). This is achieved by incrementing m. When such an element is found the comparison is carried out with the bottom half of the array. So, the pivot (k) is now compared with x[n] (n is the variable which is initially set to the bottommost element of the array). The index n is decremented till we find an element which is smaller than the pivot(k). At this stage the elements x[l] and x[n] are exchanged, and the above mentioned procedure is continued till the index m becomes larger than n. At the end the pivot is placed in the location indicated by n. The elements x[l] through x[u] are partitioned so that elements between x[l] and x[j - 1] (where j is the final index of pivot) are less than pivot and all elements between x[j] and x[u] are greater than or equal to pivot.

Example 19.1 :

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;

} */end partition */.

1. Given the following sequences of integer key values. By selecting appropriate pivot elements, sort each of these sequences in increasing order using quicksort algorithm. In each case, show the intermediate results after partitioning and count the number of comparisons and exchanges made. a) 2 17 4 19 6 1 75 43 8 21 b) 84 75 68 57 46 34 28 22 14 8 c) 5 7 8 12 43 75 84 88 94 97 d) 5 6 3 18 7 46 28 95 42 98 e) 62 55 44 52 29 36 48 57 68

19.2 NONRECURSIVE IMPLEMENTATION OF QUICKSORT

The recursive invocation of quicksort function involves the creation of a new activation record containing local data, parameters, and various other data items. Further activation of the function quicksort creates a new activation record which would have a different copy of the same data objects, addressed by the Current Environment Pointer (CEP). To avoid the overhead of routine calls in quicksort program in which execution efficiency is a significant consideration, in the following example we illustrate a nonrecursive implementation of the quicksort using a user defined stack. We will be using the stack to push the upper and lower bounds of all sub-arrays those are yet to be sorted. The information pushed in the stack is popped and processing continues until the stack becomes empty.

EXAMPLE 19.2 :

# 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 */