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