Assignment 8

• Available after Mar 29 at 4pm

This assignment is to completed individually. Please review the standards for academic integrity in the syllabus.

This assignment asks you to implement the quicksort algorithm. Then it asks you to generate some data about the performance of the insertion sort, quicksort and mergesort algorithms and create a hybrid sort.

Note: You are allowed to work on these programs on your local computer. However remember to make sure that your programs work correctly on the Khoury Linux machines. We will be grading your assignments on those machines only!

1 Quicksort

Implement the quicksort algorithm to sort an array of integers in non-descending order. Your implementation should have the following characteristics:

1.   It should choose the pivot randomly between the stated range of indices. For each time the quicksort algorithm is invoked to sort an array, it should set the seed for C's random number generator to 200.

2.   You may choose to implement either Hoare's or Lamuto's partitioning scheme.

3.   The function should have the prototype: void quicksort(int *A,int size) in a file named quicksort.h and implemented in quicksort.c .

Write tests for this algorithm in tests_quicksort.c. You are required to test the above function, but not any helper functions (e.g. the partitioning function).

2 Mirror Mirror on the Wall, Who's the Best Sort of them All?

We have learned about several sorting algorithms. It is time to see the practical performance of these algorithms, especially relative to each other. This will allow us to monitor which sorting algorithm practically works best, for random data of different sizes.

2.1 Preparation

You should start by preparing the following:

4.   Implement the in-place insertion sort algorithm as void insertionsort(int *A,int size) in

insertionsort.h and insertionsort.c . No tests are expected, but you should probably write your own to verify that your code works.

5.   Implement the mergesort algorithm (you can choose any one of top-down or bottom-up) as void mergesort(int *A,int size) in mergesort.h and mergesort.c . You may choose to use your earlier implementation and change it accordingly for this purpose.

6.   All sorting algorithms should sort in non-descending order.

7.   Write a helper function that generates random data for you: int *random_data(intn) that creates and returns an array of size n of random numbers. This will help you to quickly generate data of the required sizes. You can put this function in an appropriately chosen file.

Verify that the helper function works, and each of the sorting algorithms themselves work correctly before proceeding.

2.2 Data Generation

In this part, you should incorporate the logger provided to you earlier to measure the number of operations in each sorting algorithm. Here is the cost model you should use:

•    Each arithmetic operation on one or two integers costs 1 (e.g. add, subtract, multiply, divide, mod, etc.)

•    Each arithmetic comparison on one or two integers costs 1 (e.g. greater than, equal to, not equal to, etc.)

• Each assignment between numbers costs 1

• Each call to a function (excluding what the function does) costs 2

• A return statement costs 1

• Any other operation not covered above should cost 1

Incorporate the logger using pre-compiler directives so that it is possible to disable the logger when needed through conditional compiling.

Now generate data about the cost of each sorting algorithm to sort random data of various sizes. Keep in mind the following:

•    For a given size, make sure that you use the same data as input to all sorting algorithm. That way you can directly compare them to each other.

•    For a given size, make sure you try several sets of random data to minimize the bias of the data on the sorting algorithm. Try at least 5 sets for each size.

•    Be careful about the sizes you use. Make sure to sample small sizes well (i.e. don't jump from 2 to 500), and also make sure to include some large sizes (500000 or more).

Tabulate the costs for each sorting algorithm across different sizes. For 5 extra credit points , plot the costs as line graphs (size of array vs cost for each algorithm), so that you can compare the performance more easily!

You may choose to use Excel or any other program for the actual data tabulation and graphing.

For this part, your submission should include (at least):

8.   The code that sets up the data generation. Note that you can set up most of the above in a program, so that you don't have to actually run the program manually several times to capture all the data. You are a programmer now: why do manual work when you can automate! You do not have to write tests for this code itself, but your code should be commented, and should be free of memory leaks.

9.   A PDF document that briefly explains how you generated the data, a table of cost of each algorithm per size of the array, and finally your conclusions about which sorting algorithm is the best. Please put your conclusions in a clearly separated section, so that a reader does not have to read the entire explanation to hunt for your conclusion. Note that you do not have to conclude that one algorithm is the best of them all (chances are, it won't be!). Your conclusion must be supported by the data and a justification by you.  You can include the graphical plot(s) if you are attempting the extra credit.

3 A Hybrid sort

You may find that the mergesort algorithm takes more time than insertion sort for smaller arrays (if you do not find this in your data, you may not have enough samples of small sizes!). It may be advantageous to take a hybrid approach to sorting:

10.Start with mergesort

11.When the sub-array size becomes "small enough", switch to insertion sort to sort only that sub-array instead of continuing with mergesort.

Note that the algorithm is dynamic: it chooses to switch to insertion sort in the middle of sorting an array. This is different from choosing one algorithm or the other at the very beginning by looking at the size of the overall array. For example, the original array may be of size 10000, and yet sorting it may invoke insertion sort at several places.

The tricky part is knowing "when" to switch to insertion sort. You can use your samples from the earlier part (or generate more) to empirically determine the crossover point.

This will be a size of the input below which insertion sort is faster than mergesort, but above which mergesort is faster than insertion sort. Please note that due to sampling and randomization, you may not find a clear crossover point. But we don't need to be very accurate, so choose a point above which mergesort clearly wins.

To implement the hybrid sort, you may have to follow these steps:

12.Write a version of insertion sort with this prototype: void insertion_sort(int *A,int left,int right) . This version only sorts the array A[left..right] (indices included).

13.Write a new version of the hybrid mergesort: void hybrid(int *A,int size) , and its corresponding helper functions. This uses the mergesort algorithm normally, but switches to the above insertion sort for all sub-arrays of sizes at or below your crossover point.

With this in place, re-run the data generation from the earlier section for this hybrid. Now tabulate the results comparing only pure mergesort, and this hybrid mergesort.

For this part, your submission must include:

14.Your implementation of the hybrid sort, divided into files suitably.

15.The PDF document with the extra tabulated data, along with a brief discussion of how  you chose the crossover point and your conclusions from the data you generated. This does not have to be in a separate PDF file, but you may choose to separate this into another section .

After completing this part, you would have created your own hybrid sort!

What to Submit

Please submit the following:

• Source code, suitably styled and commented.

• Tests for the quicksort algorithm only.

• A PDF document with all the details mentioned above.

The autograder for this assignment will only check for your quicksort implementation.

This means that there is no help to determine if your code works correctly, nor will the server flag any missing files! Please make sure your submission is complete.