09.12.35 Uppbygging tölva

Programming project 3


In this project you are to write a partition function for Quicksort in IA-32 assembler language inline in Visual C++.

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()".


Return a printout in in the box at VR-II and an executable as an attachment in an email to Páll, friday november 2nd.

hh (hja) hi.is, october 24th, 2001.