Laboratory

DRAFT
This lab exercise is subject to change.

Objectives

to practise empirically analysing and comparing algorithms;
to implement quicksort with a randomised pivot;
to compare variants of quicksort.

Assessment

Deadline: 27 Janury 2019, 23:59:59
Marks: 3 + 1 bonus
Submission: give cs2521 lab07

(The bonus mark can make up for lab marks lost in other weeks!)

Quicksort Analysis (3 marks)

Write a program that reads the number of integers that need to be sorted, and then reads in the integer data, and sorts them into ascending order using quicksort and some of its variants.

Your program should accept at least one command line argument, and a second optional command line argument. The first command line argument should indicate which partitioning strategy should be used and may be either:

-pn: use a naïve pivot strategy (using the rightmost as a pivot)
-pm: use median-of-three partitioning
-pr: use a randomly-selected pivot

The second optional command line argument is -q, to indicate that the sorted data should not be printed out. This will be useful for more accurately timing data once you have tested that your sorting code sorts data correctly.

Your code should behave as follows:

./quicksort -pn
Enter data size: 5
Enter data:
5
4
3
2
1
Sorted with naive pivot:
1 2 3 4 5

./quicksort -pm
Enter data size: 4
Enter data:
900
723
1000
10000
Sorted with median of three pivot:
723 900 1000 10000

./quicksort -pr
Enter data size: 3
Enter data:
1
2
3
Sorted with randomised pivot:
1 2 3

./quicksort -pn -q
Enter data size: 5
Enter data:
99
1
100
2
1
Sorted with naive pivot:

You can use any of the code shown in lectures or tutorial for quicksort and quicksort with median-of-three pivot. You will need to make your own modifications to implement quicksort with a randomised pivot.

The code can be found here.

You must then devise and run a series of experiments to compare the properties of the 3 algorithms. At minimum you should run and time each algorithm with increasing sized data sets with ascending- and descending-ordered, and with unordered data. You should run each data set on each algorithm multiple times to get an average. You can modify or use any of the code given in lectures to generate the data.

Write up a report with your timing results for this section, and write a short discussion of your results, and compare the results for the other quicksort algorithms from this lab.

You will receive a mark for each of the following:

Implementation and analysis of results of a naïve quicksort;
Implementation and analysis of results of quicksort with median of three partitioning, and a comparison to quicksort;
Implementation and analysis of results of quicksort with a randomly-selected pivot, and a comparison to the other two approaches.

Bonus: Subfile Threshold Analysis (1 mark)

Modify your quicksort program to add two new options:

-saM: switch to insertion sort for partitions smaller than the threshold M;
-sbM: do not sort partitions smaller than the threshold M; leave them unsorted, and do an insertion sort at the end.

Perform some more timing tests. Discuss, in your report, if and/or when it improves the results.

Submitting

You must get the lab marked by your tutor in your lab.

Submit your work with the give command, like so:

give cs2521 lab07 quicksort.c qs_report.pdf

Or, if you are working from home, upload the relevant file(s) to the lab07 activity on WebCMS3 or on Give Online.