Lab Exercises Week 07

Objectives

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

Assessment

Deadline: 11:59pm Fri 3rd February

Total Marks: 3

Related Chapters of textbook

Chapter 7

Task: Quicksort - 3 Marks

Instructions: You may do this lab in pairs

Change into your lab07 directory and run the following command:

cp /home/cs1927/public_html/17x1/week07/labs/files/quicksort.c .

You have been provided 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. The program accepts 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:

Modify the above program to implement quick sort with a median of three partition and a randomised pivot. Use the pseudo-code shown in lectures for these two algorithms. 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 record all your timing results for this section in a file called timing.txt. 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.

Marking scheme: 1 Mark for each of the following :

• Implementation of quicksort with median of three partition pivot.
• Implementation of quicksort with randomised pivot.
• Analysis and comparison of results of quicksort using the three algorithms.

Submission

1927 classrun 17x1 give lab07 quicksort.c timing.txt conclusions.txt