Algorithms: Black box testing of an alleged sorting method
Paul Taylor
March 2000
This is one of the for the assessed
coursework to be handed in on 7 April 2000, and for the exam.
It is not easy.
A fellow student gives you a JAVA class file (but no source)
containing a single method
public static void student_sort (int [ ] array)
that s/he claims to be an implementation of one of the eight sorting
algorithms that were discussed in this course.
It may alter the given array, throw a exception or fail to terminate,
but you may assume that it does not interfere in any way with other
classes that are present, the operating system or any other aspect
of its environment.
You have available tools for
- generating random arrays of any given length,
- timing accurately how long student_sort takes to run,
- fitting mathematical functions to experimental data, and
- reporting how much space it consumes by allocating new arrays or objects.
You do not have available any trustworthy sorting method.
Make a list of the programming errors that are commonly made in
implementing methods like this. Design test data to give to student_sort, and explain how you would examine the possible
responses, in order to find out whether student_sort has
correctly implemented the algorithm.
If you can, identify specific kinds of programming error.
If student_sort is in fact correct,
can you tell which of the eight algorithms it is?
This is
www.PaulTaylor.EU/algorithms/blackbox.html
and it was derived from algorithms/blackbox.tex
which was last modified on 5 January 2008.