object-oriented java 2 home > sorting performance

Comparing performance of sorting algorithms

This module provides starting specifications for designing a process for investigating and comparing the performance of several classic sorting algorithms.

bookProject specification


Create a program which systematically and rigorously evaluates the performance of two different sort algorithms: one must be the bubble sort, and the second one of your choosing--probably one out of chapter 25 in the Liang9

implement the algorithms

Create a well-formed object class called Sorter which contains at least two methods, one for each of your two algorithms called something like bubbleSort(int[] arrToSort) and xxxSort(int[] arrToSort). The input type and output type should be an int[], the outputted one, of course, being the sorted array.

Carefully use the Liang9 code for your respective algorithms as your guide, and implement both the bubble sort algorithm and one of your choosing.

create client class & test

Test your two sorting algorithms by creating a client class which instantiates your Sorter class. Create a short, sample array of values, copy it so you have two individual objects, and then sort each, in in each of your methods. Verify with print calls that the array is property sorted.

Write a method in your client class that TESTS if the array passed back from each method is, in fact, sorted property. We'll need this since we'll be asking the algorithms to sort very large arrays that we cannot easily check by "hand". This method should take in an array of int values and return true or false to indicate the success or failure of the test.

create test cases

We want to test our arrays with big arrays--with lots of numbers. Create a method in your client class which uses a Random object to create an array of int values of an arbitrary length--meaning the input to this method should be an int which represents the size of the array you'd like generated.

Test your generator method by passing the generated array to each method (making a clone of each to do so) and test them with your trusty array sorting tester.

return execution times

Modify your Sorter class such that it will track the number of milliseconds required to sort any given array. You can implement this functionality in a number of ways, but the interface should be as follows:

Create a method for each of your sort algorithms called getRunTimes() that returns an array of long integers, the first being the start timestamp of the most recent call to your xxxSort method and the second being the end timestamp. The client should then be able to subtract these two values to compute a total run time for the most recent run of each algorithm.

You can get a timestamp in java several ways. A simple way is to call java.time.Instant.now().toEpichMilli() which will return the number of milliseconds since January 1, 1970 at midnight.

compare execution times

Now that you have code that can test and time two different sort algorithms, create a set of test cases to compare the functioning of your two algorithms. You will want to create a way to quantify these differences, and you can be rather mechanical about it by using a spreadsheet created like the table below, or you could be more Java-esque and create output files or just screen-based output to compare the runs of various test cases.

An important principle of test case design is to test the most obscure edge cases you can think of: such as an array that is extremely long, an array that is extremely short, one that is very unsorted, one filled with negative numbers, etc. Use the following table as a guide for writing code in your client class that runs each of your algorithms through a set of edge cases.

Prepare a github markdown page for your code's repository that describes your test and provides a summary of the results.

Test case description Time performance for bubble sort Time performance for comparison algo Describe results of test
10,000 value array with random int values

arrow_upward top

Page created in 2018 and can be freely reproduced according to the site's copyleft use agreement.