Lab Exercises Week 05

Objectives

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

Assessment

Deadline: 11:59pm Tue 19th January

Total Marks: 3 + 1 Bonus mark

Note: bonus marks can make up for lab marks lost in other weeks.

Related Chapters of textbook

Chapter 7

Quicksort - 3 Marks

Marking sheme: 1 Mark for each of the following :

• Implementation and analysis of results of quicksort
• Implementation and analysis of results of median of three partitioning and comparison to quicksort
• Implementation and analysis of results of randomised pivot and comparison to the other two algorithms

Instructions

You may do this lab in pairs

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 should be used and may be either

• -pn : use a naive pivot strategy (using the rightmost as a pivot)
• -pm : use median of three partitioning
• -pr : use a randomised 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 actually 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 for quick sort and quick sort with median of three pivot. You will need to make your own modifications to implement quick sort with a randomised pivot.

The code can be found here

You must 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 ordered, random and reverse ordered 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.

Please write all your timing results for this section in and open office spreadsheet file called timing.ods. In a text file called conclusions.txt write a paragraph at the bottom of your text file discussing your results and explaining whether the results comply with your intuitions. And compare the results for the different algorithms

To run open office spreadsheet application type at command line

soffice -calc

Write a paragraph at the bottom of your text file discussing your results and explaining whether the results comply with your intuitions. And compare the results for the different algorithms Note: The submission tests only check that your program runs and sorts the numbers of various sizes. Passing the submission tests does not mean you have implemented the different strategies correctly. However if you do not pass them, obviously something is very wrong :)

Bonus Mark

Modify your quicksort program to allow an option of -saM and -sbM where M is the subfile threhold and -sa refers to subfile strategy a and -sb refers to subfile strategy b.

The two different strategies for doing this as follows:

1. Switch to insertion sort for partitions smaller than a threshold M
2. Do not sort partitions smaller than a threshold M while quicksorting. Leave them unsorted and do one call to insertion sort at the end.

You may find that taking the insertion sort code from lectures and rewriting slightly with the following prototype will help.

void insertionSort(int a[], int l, int r);

Perform some more timing tests. Discuss when/if it improves the results. Note: There are no submission tests for the bonus stage

Submission

1927 classrun 16x1 give lab05 quicksort.c timing.ods conclusions.txt