Sort Times – Part I

sort_comparisonIn the past few weeks I have been reading and experimenting with code and exercises found in the Algorithms fourth edition book by Robert Sedgewick and Kevin Wayne. It is always a good idea for any professional in any field to refresh concepts and learn new things. In my case I am a Senior System Architect for a company in the West Coast so I constantly polish my skills in Computer Science. Hope physicians do the same thing with medical books ;o)

Many software developers tend to grab library methods to get different tasks accomplished. That makes sense. That said; it is a good idea to go back and review if the code is as optimal as needed. In my case I am comparing the performance of different sorting algorithms. If interested get a copy of Algorithms and take it for a spin.

Take a look at the following screen capture from the console of my Eclipse IDE:

main <<< alg1 ==>Shell<==

main <<< alg2 ==>Library<==

main <<<    N: 10000

main <<<    T: 200

main <<< t1:   689.00 ms

main <<< t2:   906.00 ms

main <<< Shell sort is 1.31 times faster than Library sort

I hard coded a couple implementations of sorting algorithms. In this case I chose Shell sort which is my rendition of the algorithm described in detail in the book. I also selected what I call Library sort from the java.util.Arrays package.

The test generates 10,000 random double values. I have tried with different counts. To average the time of a sort, each method is called T times (in this case 200) and yes, I have tried different values.

The total time in milliseconds for each set of executions is printed to the screen. The times are then compared to select the faster algorithm. I seem to me this is a straightforward approach to compare performance.

I have compared other sort implementations (refer to the book for additional info) and the results were as expected. I am reading and experimenting with Quicksort; so before comparing it to others I decided to test previous (and slower algorithms) against the Arrays.sort() method. I just expected it to be faster than any of the other algorithm. Quicksort seems to offer the best performance for sorts in most cases. Will find more about it in the near future and post my comments in this blog.dell_t7500

The results do not agree with what I was expecting. I ran my initial tests on a DELL Precision T7500 with two multi core 64-bit processors. The computer only had 4 GBs of RAM. I decided to install additional RAM just in case the code would be paging. I doubted that scenario since the software is quite compact. I updated the RAM
capacity up to 24 GBs.
As expected the results did not change.

Following is the test code written in Java:

package john.canessa.sort;

import java.util.Random;

public class SortCompare {

/*

* time a sorting algorithm

*/

public static double time(String alg, Double[] a) throws Exception {

double begin = System.currentTimeMillis();

switch (alg) {

case “Insertion”:

Insertion.sort(a);

break;

case “Library”:

Library.sort(a);

break;

case “Selection”:

Selection.sort(a);

break;

case “Shell”:

ShellSort.sort(a);

break;

default:

throw new Exception(“unknown alg ==>” + alg + “<==”);

}

double end    = System.currentTimeMillis();

return end – begin;

}

/*

* for specified algorithm sort N random values T times

*/

public static double timeRandomInput(String alg, int N, int T) throws Exception {

double totalTime     = 0.0;

Double[] a           = new Double[N];

Random rand          = new Random();

for (int t = 0; t < T; t++) {

for (int n = 0; n < N; n++) {

a[n] = rand.nextDouble();

}

totalTime += time(alg, a);

}

return totalTime;

}

/*

* test code

*/

public static void main(String[] args) throws Exception {

final String alg1    = “Shell”;

final String alg2    = “Library”;

final int N                = 10000;

final int T                = 200;

System.out.println(“main <<< alg1 ==>” + alg1 + “<==”);

System.out.println(“main <<< alg2 ==>” + alg2 + “<==”);

System.out.println(“main <<<    N: ” + N);

System.out.println(“main <<<    T: ” + T);

double t1     = timeRandomInput(alg1, N, T);

System.out.printf(“main <<< t1: %8.2f ms\n”, t1);

double t2     = timeRandomInput(alg2, N, T);

System.out.printf(“main <<< t2: %8.2f ms\n”, t2);

if (t1 < t2) {

System.out.printf(“main <<< %s sort is %.2f times faster than %s sort\n”, alg1, t2 / t1, alg2);

} else {

System.out.printf(“main <<< %s sort is %.2f times faster than %s sort\n”, alg2, t1 / t2, alg1);

}

}

}

The code for Shell sort is irrelevant since it appears faster. What is relevant appears to be the code for the Library sort. Such code follows:

package john.canessa.sort;

import java.util.Arrays;

public class Library {

/*

* constructor

*/

public Library() {

}

/*

* use Java library sort

*/

public static void sort(Comparable[] a) {

Arrays.sort(a);

}

/*

* show the array

*/

public static void show(Comparable[] a) {

System.out.print(“show <<< a: “);

for (int i = 0; i < a.length; i++) {

System.out.print(a[i] + ” “);

}

System.out.println();

}

/*

* test

*/

public static void main(String[] args) {

String[] a = {“Q”, “U”, “I”, “C”, “K”, “S”, “O”, “R”, “T”, “E”, “X”, “A”, “M”, “P”, “L”, “E”};

Library lib = new Library();

lib.show(a);

lib.sort(a);

lib.show(a);

}

}

The test code in the Library class was just used to test the sort() method. The results are based on the SortCompare class.

question_markIf you have comments, questions or suggestions please do not hesitate and send me a message via email. I will not use your name unless you state so.

John

john.canessa@gmail.com

Follow me on Twitter: @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *