Exercise 10: Lab assignment (due on November 22)
The objective of this assignment is to implement most sorting algorithms seen in lecture/tutorial and their variants.
This project must include at least the sorting algorithms: selection, bubble, insertion, merge (two versions), quick. All
variations and improvements to these algorithms can be integrated to this project:
o Recursive versions of: selection, bubble, insertion
o Binary insertion sort
o Improvements of Quicksort as in exercise 7 and exercise 9.
o Any other improvement that you suggest (and that you must explain)
a) Generation of data:
Arrays of integers have to be randomly generated and saved into files. A data file contains the number of elements in
the first line followed by the elements of the array separated by spaces. The algorithms must be tested on arrays of at
least 100 elements. Once submitted, your program will be tested on arrays of up to 10000 elements. You should take
this into account in the declarations.
b) Read data
When executed, your program must ask for the filename where to read the array of elements, then performs the sorting
task using every algorithm implemented. Once the array sorted, the program prints the name of the algorithm used
followed by the number of comparisons and passes to the next algorithm.
c) Statistics
In order to confirm the theoretical complexities of algorithms, you have to test the implemented algorithms on a series
of generated data and fill a table like the one in exercise 5. For example, you can use a randomly generated array of
100 elements (or more) and sort this array using all implemented algorithms. In the table, report the number of
comparisons. This experience must be repeated (10 times for example, or more). In the last three columns, report the
best case, the worst case and the average. This table is part of the assignment. You submit it as a document.
d) Submission
Submissions must be done directly on Moodle. The submission must contain (all in a zipped file):
o The folder where source files and data files are stored
o A report where you briefly explain the additional algorithms or variations implemented (document, no more
than 1 page for every algorithm or variation added)
o The statistics presented in a table (document)
Your program must be ready to be compiled/executed using the data files provided or any other data file with the same
structure (as explained in -a-).
