COMP2080 Analysis of Algorithms

The purpose of this question is to allow the student to independently compare the run time of various sorting and searching algorithms. This will allow the student to get a better understanding of time complexity. It also aims to build an appreciation of the effects that the size and organization of data have on the speed of algorithms.

The sorting algorithms that will be examined are:

1. Selection sort
2. Insertion sort
3. Merge sort
4. Quick Sort

All sorting algorithms must sort the arrays in descending order.

Each sorting and searching algorithm will be comparatively run on arrays of the following sizes:

1. fifty (50)
2. one thousand (1,000)
3. ten thousand (10,000)
4. one hundred thousand (100,000)
5. one million (1,000,000)

Each sort and search is to be tested on the same data set to strive for some consistency.

Sorting Methodology and Requirements:

1. Create a core data setcalled “coreData” which must be a single array of size one million (1,000,000) integers filled with random numbers between one (1) and two million (2,000,000).
   
   
2. For each comparative sorting test, four (4) copies(one for each sort to be tested) consisting of the same data from “coreData” must be made.  For example, if the comparative test is on one thousand (1,000) elements, four arrays of size (1000) should be made and filled with a copy of the first one thousand (1000) elements of “coreData”.

All recorded times must be measured using System.nanoTime() for consistency. An example of how to use it is given below.

long start = System.nanoTime();

//code to be tested

long end = System.nanoTime();

long timeTaken = end – start;

The unit for printing the time must be done according to the following table: