Loading...

​​Lab 5: Comparing Sorting Algorithms

​​Bard College – Computer Science – Data Structures

​​

​​In this lab we will create a program to compare different sorting algorithms on a variety of inputs. The five sorts we will explore are:

​​

• ​​insertion sort ( Insertion.sort​ )

• ​​selection sort ( Selection.sort​ )

• ​​quick sort ( Quick.sort​ )

• ​​heap sort ( Heap.sort​ )

• ​​merge sort ( Merge.sort​ )

​​Sorting Benchmark

​​Write a program that measures and reports the running times for the different sorting algorithms. At the minimum it should report the average (i.e. mean) running time for 100 experiments per configuration. You might also include support for computing the minimum, maximum, variance, and median. Use the StopwatchCPU​ to measure the running times of the sorts. Report the run-times in milliseconds.

​​Varying Input Sizes

​​Start with an array of ​​$512$​ items, and increase in powers of two, up to ​​$32,768$​ (​​$2^{15}$​).

​​Varying Input Types

​​Choose a reasonable input size and explore sorting five different kinds of input data:

1. ​​uniformly random numbers between 0-1;

2. ​​uniformly random numbers between 0-1 that are already sorted in ascending order;

3. ​​uniformly random numbers between 0-1 that are already sorted in descending order;

4. ​​random numbers between 0-1 that are mostly sorted. (You can define what mostly means);

5. ​​random numbers from the set of 1, 2, 3 and 4.

​​Submission

​​Write a report detailing your findings including tables and graphs. If you want extra Java practice, you can graph the results using the methods in textbook's StdDraw​.

​​

​​Bring a hard-copy of your lab report and code to class on Friday. Also, submit via Google Classroom a zip file that expands to a folder with at least the following two files:

​​

​​cmsc201-lab5-lastname-firstname

​​   SortingBenchmark.java 

​​   lab5.pdf

​​BONUS CHALLENGE: Mystery Sorts

​​Can you identify which sort & data-set resulted in the following results?

​​

​​size	​​sort-a	​​sort-b	​​sort-c	​​sort-d	​​sort-e
​​512	​​0.078	​​0.042	​​0.004	​​0.079	​​0.309
​​1024	​​0.173	​​0.091	​​0.006	​​0.123	​​1.186
​​2048	​​0.335	​​0.189	​​0.011	​​0.275	​​4.892
​​4096	​​0.671	​​0.373	​​0.019	​​0.574	​​19.438
​​8192	​​1.478	​​0.844	​​0.038	​​1.269	​​79.914
​​16384	​​2.985	​​1.700	​​0.080	​​2.640	​​309.903
​​32768	​​6.379	​​3.680	​​0.167	​​6.013	​​1248.194

​​