Page 259 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes j++;

if( i < j)
interchange(&x[i], &x[j]);
}
interchange(&x[m], &x[j]);
qsort(x, m, j-l);
qsort(x, j+1, n);
}
}
void interchange(int *i, int *j)
{
int temp;
temp = *i;
*i = *j;
*j = temp;
}
Choice of the Key

We can choose any entry in the list as the key. The choice of first entry is often a poor choice for
key, since if the list is already sorted, then there will be no element less than the fi rst element
selected as key, and so one of the sub-lists will be empty. Hence we choose a key near the center
of the list, in the hope that our choice will partition the list in such a manner that about half comes
on each side of key.
Therefore the function getkeyposition is:

int getkeyposition(int i, int j)
{
return(i+j mod 2);
}
The choice of the key near the center is also arbitrary, and hence it is not necessary that it will
always divide the list nicely in to half, it may also happen that one sub-list is much larger than
other. Hence some other method of selecting a key should be used. A good way to choose a key
is to use a random number generator to choose the position of next key in each activation of
quicksort.
Therefore the function getkeyposition is:

int getkeyposition(int i, int j)
{
return a random number in the range of i to j.
}
Consider the following list:
1 2 3 4 5 6 7 Indices

30 20 50 10 27 70 05

254 LOVELY PROFESSIONAL UNIVERSITY