For this project, you are required to implement the following sorting algorithms and run a benchmarking test. This will allow you to see and compare the actual running times for the algorithms we have studied and give you a deeper understanding of their inner workings. Note that you are not allowed to work in groups. All the code you submit should be your own work. We are going to use a software analysis tool to compare your code with other’s.
You are asked to implement the following sort algorithms: insertion, selection, bubble, combsort, shellsort, heapsort, mergesort, quicksort, radixsort, introsort and countingsort.
In order to evaluate all cases, you are required to read the inputs from a text file. Each line of the text file shall include 10 non-negative integers separated by a dash “-“. You are required to run this analysis for three different cases and for each case you will be provided a text file to read your inputs from. The input file for the first case, ascending.txt, will include integers that are already in ascending order. The input file for the second case, descending.txt, will include integers that are in descending order. And the file for the third case, random.txt, will include integers that are in random order. Your sort algorithms are supposed to sort the input values in ascending order.
You are also required to run a step by step analysis, meaning you shall run sorting for only the first 1000 elements, then 2000, then 4000 and so on doubling the input size in every iteration until you sort the entire set of n numbers (n=the number of integers in the file). For each iteration of sort, e.g. 1000 elements, 2000 elements etc., you are required to measure the exact running time of each algorithm and plot your timings of each algorithm (you can use excel or Google charts for your plot).