As I have mentioned before, I am going over the Algorithms fourth edition book by Robert Sedgewick and Kevin Wayne with the purpose of refreshing concepts and always learning something new. In this entry I cover my observations when using Quicksort which is one of the most popular and better performing sorting algorithms.

Before continuing reading this entry, please take a look at Sort Times – Part II. In particular take into consideration the comments in ** italics**.

The following are results taken from the console in the Eclipse IDE that I am using:

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

main <<< alg2 ==>Quick<==

**main <<< N: 1000**

**main <<< T: 200**

main <<< t1: 71.00 ms

main <<< t2: 95.00 ms

main <<< Shell sort is 1.34 times faster than Quick sort

main <<< t1: 63.00 ms

main <<< t2: 82.00 ms

main <<< Shell sort is 1.30 times faster than Quick sort

main <<< t1: 65.00 ms

main <<< t2: 95.00 ms

main <<< Shell sort is 1.46 times faster than Quick sort

main <<< alg1 ==>Quick<==

main <<< alg2 ==>Shell<==

**main <<< N: 1000**

**main <<< T: 200**

main <<< t1: 88.00 ms

main <<< t2: 62.00 ms

main <<< Shell sort is 1.42 times faster than Quick sort

main <<< t1: 103.00 ms

main <<< t2: 67.00 ms

main <<< Shell sort is 1.54 times faster than Quick sort

main <<< t1: 98.00 ms

main <<< t2: 67.00 ms

main <<< Shell sort is 1.46 times faster than Quick sort

The number of random double values used per test is 1,000. With such lower count Shellsort appears to run faster when compared with Quicksort. The arrays hold Double objects (not double primitives).

main <<< alg1 ==>Quick<==

main <<< alg2 ==>Shell<==

**main <<< N: 10000**

**main <<< T: 200**

main <<< t1: 417.00 ms

main <<< t2: 742.00 ms

main <<< Quick sort is 1.78 times faster than Shell sort

main <<< t1: 429.00 ms

main <<< t2: 741.00 ms

main <<< Quick sort is 1.73 times faster than Shell sort

main <<< t1: 483.00 ms

main <<< t2: 781.00 ms

main <<< Quick sort is 1.62 times faster than Shell sort

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

main <<< alg2 ==>Quick<==

**main <<< N: 10000**

**main <<< T: 200**

main <<< t1: 772.00 ms

main <<< t2: 453.00 ms

main <<< Quick sort is 1.70 times faster than Shell sort

main <<< t1: 737.00 ms

main <<< t2: 429.00 ms

main <<< Quick sort is 1.72 times faster than Shell sort

main <<< t1: 754.00 ms

main <<< t2: 436.00 ms

main <<< Quick sort is 1.73 times faster than Shell sort

When the number of elements in the test array increases to 10,000 Quicksort is faster than Shellsort. The same seems to hold true when the number of entries increases. I tried up to 2,000,000 entries. Not sure what would happen with larger counts.

What is interesting to me is that the following code seems to be used quite frequently in applications:

Double[] a = new Double[N];

::::

Arrays.sort(a);

Follow if the implementation of Quicksort which closely resembles the one found in the Algorithms book:

**package** john.canessa.sort;

**public** **class** QuickSort {

/*

* constructor

*/

**public** QuickSort() {

}

/*

* public sort

*/

**public** **static** **void** sort(__Comparable__[] a) {

*sort*(a, 0, a.length – 1);

}

/*

* private sort

*/

**private** **static** **void** sort(__Comparable__[] a, **int** lo, **int** hi) {

// **** check if we are done ****

**if** (hi <= lo) {

**return**;

}

// **** ****

**int** j = *partition*(a, lo, hi);

// **** ****

*sort*(a, lo, j – 1);

*sort*(a, j + 1, hi);

}

/*

* partition array

*/

**private** **static** **int** partition(__Comparable__[] a, **int** lo, **int** hi) {

**int** i = lo;

**int** j = hi + 1;

__Comparable__ v = a[lo];

// **** ****

**while** (**true**) {

**while** (*less*(a[++i], v)) {

**if** (i == hi) {

**break**;

}

}

**while** (*less*(v, a[–j])) {

**if** (j == lo) {

**break**;

}

}

**if** (i >= j) {

**break**;

}

*exch*(a, i, j);

}

*exch*(a, lo , j);

**return** j;

}

/*

* determine if v is less than w

*/

**private** **static** **boolean** less(__Comparable__ v, __Comparable__ w) {

**return** __v____.compareTo(____w____)__ < 0;

}

/*

* exchange the elements in array

*/

**private** **static** **void** exch(__Comparable__[] a, **int** i, **int** j) {

__Comparable__ temp = a[i];

a[i] = a[j];

a[j] = temp;

}

/*

* check if array is sorted

*/

**public** **static** **boolean** isSorted(__Comparable__[] a) {

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

**if** (!*less*(a[i – 1], a[i])) {

System.** out**.println(“isSorted <<< a[” + (i – 1) + “]: ” + a[i – 1] + ” a[” + i + “]: ” + a[i]);

**return** **false**;

}

}

**return** **true**;

}

}

The Library class 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();

}

}

The points that I got after experimenting with the different sorting algorithms is:

Understand the performance and limitations of sorting algorithms. |

Keep around tested implementations of sorting algorithms. |

Always test the selected sorting algorithm using typical data. |

Always compare sorting algorithms to make sure they perform as expected. |

Let academics determine the performance characteristics of sorting algorithms. |

If needed, interface to sorting algorithms written in more efficient languages (e.g., C). |

If you have comments or questions in this or any other blog entry, please send me a message via email. I will not disclose your name unless you explicitly let me know.

John

john.canessa@gmail.com

Follow me on Twitter: **@john_canessa**