Page 258 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 12: Sorting

The sorted list b is Notes

80 68 62 16 12
The elements of the merged list are
80 68 63 62 50 25 20 16 12 10

Task Write a C program for merge sort.

12.7 Quick Sort

In this method an array a[1],.....,a[n] is sorted by picking some value in the array as a key element,
we then swap the fi rst element of the list with the key element so that the key will come in the

first position, we then find out the proper place of key in the list. The proper place is that position

in the list where if key is placed then all elements to the left of it are smaller than the key, and all
the elements to the right of it are greater than the key. To obtain the proper position of the key we
traverse the list in both the directions using the indices i and j respectively. We initialize i to that
index which is one more than the index of the key element, i.e. if the list to be sorted is having
the indices running from m to n, then the key element is the at index m, hence we initialize i to
(m+1). The index i is incremented till we get an element at the ith position greater than the key
value. Similarly we initialize j to n and go on decrementing j till we get an element having the
value less than the key value. We then check whet her i and j have crossed each other. If not then
we interchange the elements at the ith and jth position, and continue the process of incrementing
i and decrementing j till i and j crosses each other. When i and j crosses each other we interchange
the elements at the key position(i.e. at mth position) and the elements at the jth position. This

brings the key element at the jth position, and we find that the elements to left are less than and
the elements to the right of it are greater than it. Therefore we can split the given list into two
sub-lists. The first one made of elements from mth position to the (j-1)th position, and the second

one made of elements from the (j+1)th position to nth position, and repeat the same procedure
with each of the sub-lists separately.
Here is a C implementation.
void qsort(int x[], int m, int n)
{
int key,i,j,k;
if(m < n)
{
k = getkeyposition(x, m, n);
interchange(&x[m], &x[k]);
key = x[m];
i = m + 1;
j =n;
while(i < j)
{
while((i <= n) && (x[i] <= key))
i++;
while(j >= m) && (x[i] > key))

LOVELY PROFESSIONAL UNIVERSITY 253