UQ Students should read the Disclaimer & Warning
Note: This page dates from 2005, and is kept for historical purposes.
<!DOCTYPE HTML PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<!--
Copyright © 2004 Ned Martin
http://copyright.the-i.org/
Magic.
-->
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="Description" content="Description." />
<meta name="Keywords" content="key, words" />
<title>COMP2502 – Assignment 1</title>
</head>
<body>
<h1>COMP2502 – Assignment One – Sorting </h1>
<p>For which I achieved 105 out of 100. </p>
<p><a href="#spec">Specification</a> | <a href="#subm">My Submission</a> | <a href="#results">My
Results</a> </p>
<h2 id="spec">Specification</h2>
<p>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%. </p>
<p>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. </p>
<h3>Sorting </h3>
<p>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: </p>
<ol>
<li> 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. </li>
<li> Write code to generate various test cases for the sorting algorithms including:
<ul>
<li> randomly ordered data, </li>
<li> ordered data, </li>
<li> reverse-order data. </li>
</ul>
</li>
<li> Modify the example programs given below to <em>time </em>both sorting algorithms
for each of your test cases. </li>
<li><em>Time </em>both algorithms over all cases for a set of different n . </li>
<li> For each algorithm and case create a table headed n <em>, </em>log 2 n <em>, </em>n
log 2 n <em>, </em>n 2 <em>, Time </em>and fill in each row with the </li>
<li>appropriate numbers. </li>
<li> Try and estimate the asymptotic behavior of the algorithms for each case. </li>
<li> 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? </li>
</ol>
<h3>Algorithms and Code </h3>
<p>The following public algorithms do a sort of elements of an array. </p>
<pre>
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
</pre>
<p>Example code for using these sorters are contained in the file:</p>
<pre>http://www.itee.uq.edu.au/˜comp2502/java/Example.java </pre>
<p>Follow the example given to construct the necessary code for this assignment. </p>
<p>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. </p>
<p>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. </p>
<p>Your report should be at most 5 pages long, but length is less important than
the mark scheme. </p>
<p>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. </p>
<p>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. </p>
<h3>Assessment Criteria </h3>
<p>Your assignment will be assessed on the following points: </p>
<ul>
<li> 10% on the asymptotic analysis. </li>
<li> 25% on production of appropriate code. </li>
<li> 25% on the generation of data, the selection of appropriate n and the production
of results. </li>
<li> 40% on the analysis of the results. </li>
</ul>
<h2 id="subm">My Submission</h2>
<p><a href="COMP2502-A1.pdf">Analysis of Results</a> (PDF File, 235 <acronym title="Kilobyte">KB</acronym>) </p>
<p> Example.java (Sorting test framework)<br />
<textarea cols="82" rows="629" readonly="readonly">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</textarea>
</p>
<h2 id="results">My Results</h2>
<table>
<tr>
<td colspan="2"><strong>Asymptotics </strong></td>
<td>10 </td>
</tr>
<tr>
<td colspan="2"><strong>Questions 2 and 3 </strong></td>
<td>25 </td>
</tr>
<tr>
<td colspan="2"><strong>Questions 4 and 5 </strong></td>
<td>25 </td>
</tr>
<tr>
<td colspan="2"><strong>Analysis </strong></td>
<td>40 </td>
</tr>
<tr>
<td colspan="2"><strong>Comments </strong></td>
<td>Wow!!! Everything was excellent. </td>
</tr>
<tr>
<td colspan="2"><strong>Bonus </strong></td>
<td>5 </td>
</tr>
<tr>
<td colspan="2"><strong>Total </strong></td>
<td>105 </td>
</tr>
</table>
<p>27-Dec-2004</p>
</body>
</html>