Description
Objective
Students will be able to conduct a comparison study of the performance of sorting algorithms, by
implementing an experiment to compare the running times of well-known sorting algorithms.
Assignment Problem
Design and implement an experiment to compare in real time the running times of the following sorting algorithms:
– bubble sort
– insertion sort
– merge sort
– quicksort
– selection sort
An implementation of quicksort is given in a separate file. Time the sorting algorithms several times
each, and save the results in a .csv file that can be open in an Excel file later. Format your .csv file
as follows:
…
(r.t. stands for running time)
Time not less than 1000 runs of these algorithms (you should have a similar number of lines in your .csv
file). To time your code, you can use any of the Java utilities discussed in class, i.e. System.
currentTimeMillis(), System.nanoTime(), or (new Date()).getTime().
Use Excel to depict graphically the results of your experiment.
What did you observe?
Guidelines
The assignment is to be completed individually. The given problem is based on the content studied in
class on sorting algorithms.
You are allowed to use all of the code discussed in the lectures. In those cases, make sure you properly
credit its source.
Design
Students are expected to structure the code as indicated in the UML class diagram:
Main
+static void main(String[] args)
+Main()
SortingAlgorithms
+static void bubbleSort(int[] list)
+static void fillArray(int[] list)
+static void printArray(int[] list)
+static void insertionSort(int[] list)
+static void selectionSort(int[] list)
+static void quickSort(int[] list)
+static void mergeSort(int[] list)
Deliverables:
• A compressed folder, PID Assignment 3 (e.g. 1234567 Assignment 3), containing
– all of the source code of the exercise (the .java files; do not include other files or folders
generated by the IDE)
– a document explaining what you observed in the experiment and your conclusions. This
document will include the text of your explanations and the picture(s), chart(s), or diagram(s)
obtained in Excel.
– the .csv file
– the Excel file
Except for the .csv and the Excel documents, make sure you write your Panther ID as the first line of
each file you submit (given as a comment in the Java files). Do not include your name in any of the
deliverables.