UQ Students should read the Disclaimer & Warning

Note: This page dates from 2005, and is kept for historical purposes.

# COMP2502 – Assignment One – Sorting

For which I achieved 105 out of 100.

Specification | My Submission | My Results

## Specification

Due via ITEE online submission by 5pm, Wenesday 8 September. Assignments handed in 48 hours or more before deadline (i.e., by Monday 6 September, 5pm) will score a bonus of 5%.

The main focus of this assignment is on understanding how a theoretical algorithm analysis translates into variation of run time of an algorithms as n grows.

### Sorting

In the following subsections you will be given Java implementations of some standard sorting algorithms as well as some associated code which gives examples of timing calls to the algorithms. In this assignment you are expected to do the following:

- Do an asymptotic analysis of the algorithms and find the order of the algorithms. If you find an analysis e.g. in a text book, feel free to use it but make it clear where you found it. Failure to cite a reference when using someone else’s work is plagiarism.
- Write code to generate various test cases for the sorting algorithms including:
- randomly ordered data,
- ordered data,
- reverse-order data.

- Modify the example programs given below to
*time*both sorting algorithms for each of your test cases. *Time*both algorithms over all cases for a set of different n .- For each algorithm and case create a table headed n
*,*log 2 n*,*n log 2 n*,*n 2*, Time*and fill in each row with the - appropriate numbers.
- Try and estimate the asymptotic behavior of the algorithms for each case.
- Analyse your results and try and comment on what you think is happening. How are the algorithms behaving versus the asymptotic order? Which algorithm would be better for which cases?

### Algorithms and Code

The following public algorithms do a sort of elements of an array.

http://www.itee.uq.edu.au/˜comp2502/java/StandardFirstSorter.java http://www.itee.uq.edu.au/˜comp2502/java/AbstractFirstSorter.java http://www.itee.uq.edu.au/˜comp2502/java/AbstractSorter.java http://www.itee.uq.edu.au/˜comp2502/java/MedianOfThreeSorter.java http://www.itee.uq.edu.au/˜comp2502/java/SISorter.java http://www.itee.uq.edu.au/˜comp2502/java/Sorter.java

Example code for using these sorters are contained in the file:

http://www.itee.uq.edu.au/˜comp2502/java/Example.java

Follow the example given to construct the necessary code for this assignment.

Since the primary focus of the assignment is not on coding, if you have any questions about how to generate test data and time your code, feel free to post them on the newsgroup.

The major focus in assessing your code will be on how well it addresses your strategy for measuring the algorithms. You should write a report in which you explain your strategy, produce a table as described here of run times of the various algorithms versus possible asymptotic complexities, and use this information to relate the algorithms’ actual performance to theoretical results.

Your report should be at most 5 pages long, but length is less important than the mark scheme.

You should hand in the report in PDF format, and one Java file, containing code to time the algorithms. This file should call the provided sorting algorithms, and should work with the versions we have provided so we can test your code against ours.

It is possible to generate PDF from lab computers http://help.itee.uq.edu.au/printing/ps2pdf.html but you should make sure you can do so well before the deadline.

### Assessment Criteria

Your assignment will be assessed on the following points:

- 10% on the asymptotic analysis.
- 25% on production of appropriate code.
- 25% on the generation of data, the selection of appropriate n and the production of results.
- 40% on the analysis of the results.

## My Submission

Analysis of Results (PDF File, 235 KB)

Example.java (Sorting test framework)

## My Results

Asymptotics |
10 | |

Questions 2 and 3 |
25 | |

Questions 4 and 5 |
25 | |

Analysis |
40 | |

Comments |
Wow!!! Everything was excellent. | |

Bonus |
5 | |

Total |
105 |

27-Dec-2004