Instructions

The exercise aims to develop your insight into the performance of algorithms. We look at both the actual running time of algorithms (in milliseconds of CPU usage) and the complexity of algorithms (in terms of operations performed), and compare and contrast them. The main emphasis is not so much on coding but is on understanding the performance of the algorithms and why they perform well and poorly on different inputs. To understand the performances you may need to consult the textbook in the area. We shall deal with the process of sorting of lists of integers into ascending order and shall compare the performance of three sorting algorithms in Java:

• Insertsort,
• Mergesort
• Quicksort

We are interested in two aspects of performance:

1. How the performance varies as the size of the input increases, i.e. the rate of growth of the performance measures.
2. How the algorithms perform on special kinds of lists, e.g. those already ascending, or descending order, and those in which there are few items repeated many times.

For the rate of growth we will display the results as graphs of performance as input size varies. You should produce your methods in a file Complexity.java in class Complexity.

Part 1 - Creating a list of random numbers

In order to assess the performance as the size of the input lists increases, you are asked to provide a routine for generating lists of numbers of arbitrary size whose items are randomly generated. To do so you need to generate random numbers. The length of the list should be a parameter that we can change to assess the running time of the various sorting algorithms.

Note: In Java, to generate random numbers you may either use the class Random in the API and its methods, or the method random in package Math (see API documentation for details).

Part 2 - Creating arrays

Create a method to generate ascending and descending lists of integers (consecutive is fine). Write a method to generate ascending and descending lists of integers (simply consecutive integers will do). Also write a method to generate lists which consists of a few items many times repeated. To do this you may use the random list generator from Task 1, but restrict the possible integers to a small range, say 0-9

Part 3 - Sort Methods

Provide code for the three sorting methods Insertsort, Mergesort and Quicksort. You may write these from scratch, or get them from textbooks, or from Java libraries or from websites dealing with algorithms.

Part 4 - Timing Analysis

Perform timing analysis on the three sorting algorithms on the various types of lists that you created in part 1 and part 2. The goal in this step is to find the running time of the program. You can time your programs using a simple approach such as the following. You should run each sorting algorithm on the various types of lists of increasing lengths. The actual lengths of the lists for realistic timing in milliseconds depend (of course) on the speed of your processor. A maximum length of 5,000 or 10,000 may be appropriate, but on slower processors this may be too large. Experiment! Create about 10 lists of lengths evenly spaced up to the maximum. Record your timing results. You can do this by having your program write the results to a file or you can simply track and plot them manually in Excel or another program.

long startTime = System.nanoTime(); //Current System Time at start methodToTime(); //replace this with your method call long endTime = System.nanoTime(); //Current system Time at end long duration = (endTime - startTime); //divide by 1000000 to get milliseconds. 

Part 5 - Analysis

In approximately one page document your observations. Summarize the test cases that you ran and what occurred during their execution. What did you conclude by completing this lab exercise. Include any graphs to support your rationale. Also any challenges that you encountered in your write up and how you were able to overcome them.

Be sure to submit both your source code and the document. Marks are allocated not just for running code but for your understanding and explanation of the performance of algorithms. So be prepared to give clear explanations to the demonstrator.

NEED PICTURES OF CODE AND RESULTS!!!!