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:

1. 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.
2. Write code to generate various test cases for the sorting algorithms including:
   • randomly ordered data,
   • ordered data,
   • reverse-order data.
3. Modify the example programs given below to time both sorting algorithms for each of your test cases.
4. Time both algorithms over all cases for a set of different n .
5. 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
6. appropriate numbers.
7. Try and estimate the asymptotic behavior of the algorithms for each case.
8. 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)
import java.io.*; import java.util.*; import java.lang.*; /** * Creates test data for algorithms and then runs and times the algorithms. * * The algorithms sort specifically ordered data in a specified manner and * print the time taken to sort in milliseconds, averaged over the number of * times run. * * Command line arguments for the program are as follows: * -(q|p) AVERAGE (1|2|3) (1|2|3) N {(1|2|3) (1|2|3) N} * -n AVERAGE (1|2|3) (1|2|3) N {N} * -m AVERAGE (1|2|3) (1|2|3) N {N} MULTIPLIER * Where AVERAGE is the number of times to run the sort, over which the * result is averaged, N is the length of the sequence to sort and * MULTIPLIER is a value by which each N is multiplied. * The first (1|2|3) identifies the sequence used, 1 for random, two for * ordered, 3 for reverse, and the second (1|2|3) specifies the sorting * algorithm: 1 for StandardFirstSorter, 2 for MedianOfThreeSorter and 3 * for SISorter. Specifying the -p flag will print the sequence used, * both before and after sorting. Output from the program is formatted * as comma separated values, suitable for manipulation by programs such * as Microsoft Excel * * @author Ned Martin * @version 2004-SEP-05:SUBMIT * * Tabstops are 8-spaced. */ public class Example { /** * ArrayList to store measured times. */ private static ArrayList storedTimes = new ArrayList(); /** * Add times to an ArrayList. * * @param long milliseconds time to store. * @param integer row to add. */ private void addTimes ( long milliSeconds, // time to store int row // row to store in ) { // offset by zero in array row = row - 1; // check if value is already in array if (storedTimes.size() > row) { milliSeconds += ((Long)storedTimes.get(row)).longValue(); storedTimes.set(row, new Long(milliSeconds)); } // this is the first element so add it else { storedTimes.add(new Long(milliSeconds)); } } // end addTimes /** * Parse arguments and format nicely. * * @param boolean input type flag. * @param boolean multiplier flag. * @return String formatted nicely. */ private static String englishIfy ( boolean inputType, // input type flag boolean multiplier, // multiplier flag String[] args // args to parse ) { String string = new String(); // if using new input type if (inputType) { int subtractor = 0; int multiplierValue = 1; // we are using a multiplier if (multiplier) { subtractor = 1; // get the last arg value as a multiplier multiplierValue = Integer.parseInt(args[args.length - 1]); } for (int ii = 4; ii < (args.length - subtractor); ii++) { string = string + "(" + englishIfier(1, args[2]) + " " + englishIfier(2, args[3]) + " " + (Integer.parseInt(englishIfier(3, args[ii])) * multiplierValue) + "), "; } } // old input type else { for (int ii = 2; ii < args.length; ii+=3) { string = string + "(" + englishIfier(1, args[ii]) + " " + englishIfier(2, args[ii + 1]) + " " + englishIfier(3, args[ii + 2]) + "), "; } } return string; } // end englishIfy /** * Lookup values and return appropriate String values. * * @param integer number of input field. * @param String value of field. * @return String formatted sensical data. */ private static String englishIfier ( int fieldNumber, // number of input field String fieldValueString // value in this field ) { /** * int, int, num_length * dataType, sortAlgorithm, dataLength * field: 1, 2, 3 * value: */ int fieldValue = Integer.parseInt(fieldValueString); switch (fieldNumber) { // dataType case 1: // find which data type is being used switch (fieldValue) { case 1: return "Random"; case 2: return "Ordered"; case 3: return "Reverse"; } break; // sortAlgorithm case 2: // find which sorting algorithm is being used switch (fieldValue) { case 1: return "Standard"; case 2: return "Median"; case 3: return "SISorter"; } break; // data length case 3: return fieldValue + ""; } // we should never get here return "englishIfy: Error " + fieldNumber + ", " + fieldValueString; } // end englishIfy /** * Create an array of random integers within a given range. * * @param integer length of array to create * @return array of random integers or given length */ private int[] randomData ( int dataLength // length of data ) { // create an array to hold data int[] data = new int[dataLength]; // create a Random object // note: we seed Random so the sequence is the same every time // for a given datalength Random rand = new Random(dataLength); // add random-ordered data between 1 and dataLength for (int ii = 0; ii <dataLength; ii++) { data[ii] = rand.nextInt(dataLength) + 1; } return data; } // end randomData /** * Create an array of ordered integers within a given range. * * @param integer length of array to create. * @return array of ordered integers. */ private static int[] orderedData ( int dataLength // length of data ) { // create an array to hold data int[] data = new int[dataLength]; // add ordered data for (int ii = 0; ii <dataLength; ii++) { data[ii] = ii + 1; } return data; } // end orderedData /** * Create an array of reverse-ordered integers of given length. * * @param integer length of array to create. * @return array of reverse ordered integers. */ private static int[] reverseData ( int dataLength // length of data ) { // create an array to hold data int[] data = new int[dataLength]; // add reverse-ordered data for (int ii = 0; ii <dataLength; ii++) { data[ii] = dataLength - ii; } return data; } // end reverseData /** * Create an array of integers ordered in a given manner. * * @param integer type of ordering to use. * @param integer length of array to create. * @return array of integers ordered in a given manner. */ private int[] createData ( int dataType, // type of data to create int dataLength // amount of data to create ) { /** * Random-ordered Data = 1 * Ordered Data = 2 * Reverse-ordered Data = 3 */ switch (dataType) { // create random data case 1: return randomData(dataLength); // create ordered data case 2: return orderedData(dataLength); // create reversed data case 3: return reverseData(dataLength); // exit if we have reached here default: System.err.println("dataType: Invalid data type " + dataType); System.exit(1); } // we never get here return null; } // end createData /** * Sort a given array of integers with a given sorting algorithm. * * @param integer algorithm to sort with. * @param array of integers to sort. * @return long time taken to sort in milliseconds. */ private long sortData ( int sortAlgorithm, // algorithm to use int[] data // data to sort ) { Sorter sorter = null; /* * StandardFirstSorter = 1 * MedianOfThreeSorter = 2 * SISorter = 3 */ switch (sortAlgorithm) { case 1: sorter = new StandardFirstSorter(); break; case 2: sorter = new MedianOfThreeSorter(); break; case 3: sorter = new SISorter(); break; default: System.err.println("sortData: invalid sort algorithm " + sortAlgorithm); System.exit(1); } // set a start time long runtime = System.currentTimeMillis(); // sort the data sorter.sort(data); // return the total time taken return System.currentTimeMillis() - runtime; } // end sortData /** * Sort specifically ordered data in a specified manner and print the * time taken to sort in milliseconds. * * @param boolean whether or not to print data. * @param integer data type to sort. * @param integer algorithm to sort with. * @param integer length of data to sort. */ public Example ( int row, // current row processing boolean hideData, // print data or not int dataType, // data type to sort int sortAlgorithm, // algorithm to sort with int dataLength // length of data to sort ) { // create an array of integers of given length and sorting int[] data = createData(dataType, dataLength); // print unsorted data if (!hideData) { for (int i = 0; i < data.length; i++) { System.out.print(data[i] + " "); } System.out.println(""); } // sort the data long runtime = sortData(sortAlgorithm, data); // print sorted data if (!hideData) { for (int i = 0; i < data.length; i++) { System.out.print(data[i] + " "); } System.out.println(""); } // print time taken to sort if (!hideData) { System.out.println("The time to run was " + runtime); } else { System.out.print(runtime + ", "); } addTimes(runtime, row); } // end Example /** * Prints an invalid args message and exits. */ private static void invalidArgs() { System.err.println("Invalid args: Command line arguments for the program are as follows:\n" + "-(q|p) AVERAGE (1|2|3) (1|2|3) N {(1|2|3) (1|2|3) N}\n" + "-n AVERAGE (1|2|3) (1|2|3) N {N}\n" + "-m AVERAGE (1|2|3) (1|2|3) N {N} MULTIPLIER\n" + "Where AVERAGE is the number of times to run the sort, over which the\n" + "result is averaged, N is the length of the sequence to sort and\n" + "MULTIPLIER is a value by which each N is multiplied.\n" + "The first (1|2|3) identifies the sequence used, 1 for random, two for\n" + "ordered, 3 for reverse, and the second (1|2|3) specifies the sorting\n" + "algorithm: 1 for StandardFirstSorter, 2 for MedianOfThreeSorter and 3\n" + "for SISorter. Specifying the -p flag will print the sequence used,\n" + "both before and after sorting. Output from the program is formatted\n" + "as comma separated values, suitable for manipulation by programs such\n" + "as Microsoft Excel"); System.exit(1); } // end invalidArgs /** * The algorithms sort specifically ordered data in a specified manner * and print the time taken to sort in milliseconds, averaged over the * number of times run. * * Command line arguments for the program are as follows: * @param -(q|p) AVERAGE (1|2|3) (1|2|3) N {(1|2|3) (1|2|3) N} * @param -n AVERAGE (1|2|3) (1|2|3) N {N} * @param -m AVERAGE (1|2|3) (1|2|3) N {N} MULTIPLIER * Where AVERAGE is the number of times to run the sort, over which the * result is averaged, N is the length of the sequence to sort and * MULTIPLIER is a value by which each N is multiplied. * The first (1|2|3) identifies the sequence used, 1 for random, two for * ordered, 3 for reverse, and the second (1|2|3) specifies the sorting * algorithm: 1 for StandardFirstSorter, 2 for MedianOfThreeSorter and 3 * for SISorter. Specifying the -p flag will print the sequence used, * both before and after sorting. Output from the program is formatted * as comma separated values, suitable for manipulation by programs such * as Microsoft Excel * * @return integer 0 on success. * @return integer 1 otherwise. */ public static void main (String args[]) { int runTimes, // number of times to run dataType = 0, // data type to sort sortAlgorithm = 0, // algorithm to sort with dataLength = 0; // length of data to sort boolean multiplier = false, // use a multiplier inputType = false, // second input type hideData = true; // to print data or not // minimum amount of args must be 5 if (args.length < 5) { invalidArgs(); } // check input type if (args[0].equals("-n")) { // -n AVERAGE (1|2|3) (1|2|3) N {N} // use different parsing here inputType = true; } else if (args[0].equals("-m")) { // -m AVERAGE (1|2|3) (1|2|3) N {N} MULTIPLIER if (args.length < 6) { invalidArgs(); } // use different parsing here inputType = true; // use a multiplier multiplier = true; } else // args[0].equals("-q" or "-p") { // check if args are invalid for this format // -q AVERAGE (1|2|3) (1|2|3) N {(1|2|3) (1|2|3) N} if (!((args.length - 2) % 3 == 0)) { invalidArgs(); } } if (args[0].equals("-p")) { // -p AVERAGE (1|2|3) (1|2|3) N {(1|2|3) (1|2|3) N} // continue to next else // print the data hideData = false; } // parse commandline arguments runTimes = Integer.parseInt(args[1]); // if using second input type if (inputType) { dataType = Integer.parseInt(args[2]); sortAlgorithm = Integer.parseInt(args[3]); } System.out.println("Running test " + runTimes + " times"); // print title explaining what's going on System.out.println(englishIfy(inputType, multiplier, args)); // loop the amount of times we are running the algorithm(s) for (int ii = 0; ii < runTimes; ii++) { // second input type if (inputType) { // if using a multiplier from input if (multiplier) { // last commandline argument is a multiplier int multiplierValue = Integer.parseInt(args[args.length - 1]); // for every n from the commandline minus the last one which is a multiplier for (int jj = 4; jj < (args.length - 1); jj++) { // run the sorter dataLength = Integer.parseInt(args[jj]) * multiplierValue; Example sortData = new Example((jj - 3), hideData, dataType, sortAlgorithm, dataLength); } } else { // for every n on the commandline for (int jj = 4; jj < args.length; jj++) { // run the sorter dataLength = Integer.parseInt(args[jj]); Example sortData = new Example((jj - 3), hideData, dataType, sortAlgorithm, dataLength); } } } // manually specified individual arguments else { // for every third n on the commandline (2, 5, 8, ...) for (int jj = 2; jj < args.length; jj+=3) { // get the args: dataType sortAlgorithm dataLength dataType = Integer.parseInt(args[jj]); sortAlgorithm = Integer.parseInt(args[jj + 1]); dataLength = Integer.parseInt(args[jj + 2]); // run the sorter Example sortData = new Example(((jj + 1) / 3), hideData, dataType, sortAlgorithm, dataLength); } } System.out.println(""); } // calculate averages // rows = (args.length - 2) / 3 System.out.println("Total time for " + runTimes + " runs"); // print title explaining what's going on System.out.println(englishIfy(inputType, multiplier, args)); // print total times for (int ii = 0; ii < storedTimes.size(); ii++) { System.out.print(storedTimes.get(ii) + ", "); } System.out.println("\nAverage time"); // print title explaining what's going on System.out.println(englishIfy(inputType, multiplier, args)); // print average times for (int ii = 0; ii < storedTimes.size(); ii++) { System.out.print( ((Long)storedTimes.get(ii)).longValue() / runTimes + ", "); } } // end main } // end Example

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