ECM1414 Data Structures and Algorithms
Requirement
In this exercise you will implement two sorting algorithms and compare their computational complexities, as measured by the number of comparisons, expressed as a function of the length of the list being sorted.
1. Implement the following (see lecture notes for guidance):
lessThan(x, y), which performs a standard comparison operation (using “x < y”) and increases the global number of comparisons by 1. You should use this function instead of x < y in the following functions so that you have an easy way of counting comparison operations for the complexity analyses. insert(item, list), which uses the straight (linear) insertion method to insert an element item into a sorted list list.
insertSort(list), which sorts a list list by insertion, using the insert function. split(list, list, list), which splits a list in the middle into two (see lecture notes for the detailed description).
merge(list, list), which merges two sorted lists, and return the merged list.
mergeSort(list), which sorts a list by recursive merging.
randomList(n), which generates a list of random integers, of length n specified by the user (the integers should be in the range [-10n, +10n]).
2. Use these procedures to write a function listdemo(n), which demonstrates the above functions by generating a random list of length n, sorting it by both insertSort and mergeSort, and printing the original unsorted list and the number of comparisons made in each case.
In your hard-copy submission you should include print-outs of four runs of listdemo(n), with n = 25, 50, 75, 100.
3. Now for n = 200, 400, 600, 800, 1000 generate 5 random lists of length n and tabulate the number of comparisons made in sorting each list both by insertSort and by mergeSort. Plot these results in a graph, clearly distinguishing between data for insertSort and data for mergeSort (e.g., using different symbols or colours). Your graph should have n, the length of the list, plotted along the horizontal axis, and the number of comparisons plotted along the vertical axis.
In the same graph, for each n, plot the number of comparisons for sorting (a) the already sorted list
[1, 2, 3, … , n], and (b) the reverse-sorted list [n, n - 1, … , 2, 1], using both sorting methods.
4. Assuming that the average-case and worst-case complexity functions of the two sorting algorithms are of the form. an2 (linear insert sort) and bn log2 n (merge sort) respectively, use your data to form. empirical estimates of the coefficients a and b. To this end, you may and it helpful to tabulate the values of cn=n2 and cn=(n log2 n), where cn is the number of comparisons.
Also use your data to form. a hypothesis about the best-case complexities for the two algorithms.
5. Comment on your results, with reference to the theoretical complexity analyses of the algorithms used, best and worst cases, and the choice of complexity measure. To what extent is the theory borne out in practice? What have you learnt from this exercise that will be useful in future?