T÷lvunarfrŠ­i 2

Weekly note 11

Last week we started on Quicksort from Chapter 7. This week, which is split by Easter break, we will look in more detail at Quicksort and see some versions of it that fix problems that it has with certain types of input.

Next week (i.e. April 4th-8th) we will start on priority queues from Chapter 9.

Programming project 2

In this second programming project you are to look at the sorting functions that come with the operating systems Windows and Linux, and the programming language C++. You are to compare them on a few types of input and see if you can write your own sort function that runs faster.

The function qsort originally came with the operating system Unix. It is written in the programming language C, which is obvious from its interface. It has now been standardized and now also included int the library stdlib.h. There is a clear description of the function and its use in the MSDN documentation that comes with the Visual C++ compiler. Also there is a man-page that comes with Linux with a good description. The main thing to notice about qsort is that it uses a comparison function, that you have to define and provide as a parameter to the function. This comparison function takes two parameters and returns a negative number (e.g. -1) if the first parameter is less than the second one, 0 if the parameters are equal, and it returns a positive number if the first parameter is larger than the second one. Another parameter to qsort is the size of the array elements in bytes. You can find the size of different types with the sizeof function.

The function sort is in a program library that comes with the programming language C++. This library used to be called STL (Standard Template Library), but now it is just a part of what is called C++ Standard Library. To use the sorting function you need to use "#include <algorithm>". You can use sort on ordinary array by supplying the address of the first array element as the first parameter and the address behind the last element as the second parameter. Example:

   #include <algorithm>
   using namespace std;
   int a[100];
   sort( &a[0], &a[100] );

You are also to write your own sortint function and try to do better than these two system function. It is probably a good idea to base your function on Quicksort, but you can choose which of the improvements you make on the function from the book. Describe in detail the changes you do, it is something other than described in the textbook.

Compare these three sorting function on the following types of input:

  1. Almost sorted array. About 0.01% of the items are not in the right place.
  2. Almost sorted in reverse order. About 0.01% of the items are not in the right place based on reverse order.
  3. Only 100 different values, that are distributed equally in the array (use for example "a[i] = rand() % 100;").
  4. Equally distributed random numbers in the range 0 to n-1.
You will have the make up the data yourselves. To get you on the right track you are supplied a function that generates the first type of input. The size of the input might need to be rather large. It is not unlikely that you will have to sort 10 million items (or even more) to get a useful time.

Those who manage to write a sorting function that is faster than qsort and sort on all four input types get an extra point for this project.

Write a report on the implementation of the time measurements and their results, in additon to a printout of the program to your section teacher before 6pm on friday April 8th. They will not accept later submissions.

annaing (hja) hi.is / hh (hja) hi.is, March 21st, 2005.