A large portion of time in Quicksort is spent in partitioning the elements around a pivot element. It is therefore important that this section of the program is fast for the whole method to be fast. Below is an implementation of Quicksort in C++.
void quicksort( int *a, int l, int r)
{
if (r <= l) return;
int i = partition(a, l, r);
quicksort(a, l, i-1);
quicksort(a, i+1, r);
}
There are many versions of the partition function, but we will us a method
that partitions around the rightmost element.
int partition(int *a, int l, int r)
{
int i = l-1, j = r;
int v = a[r];
for (;;) {
while (a[++i] < v) ;
while (v < a[--j]) if (j == l) break;
if (i >= j) break;
exch(a[i], a[j]);
}
exch(a[i], a[r]);
return i;
}
The function exch swaps the values of two memory locations. You
do not have to have that as a separate function.
You are to write the partition function in IA-32 assembly language, so that all the code in the function is in assembly language. The only thing that can be in C++ is the function header and the local variable declarations. Also write a main program that calls Quicksort to sort a 100.000 element random array. Make the random number with "rand()*32768 + rand()".
hh (hja) hi.is, october 24th, 2001.