Tölvunarfræði 2

Weekly note 11

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

Programming project 2

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.

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.