From LiteratePrograms

Other implementations: AWK | C | C++ | Eiffel | Erlang | Forth | Haskell | Java | JavaScript | Mathematica | Mercury | Oz | Python | Python, arrays | Scala | Sed | Standard ML | Visual Basic .NET | XProc

Contents 1 Overview 2 Implementation 3 Unit Tests 4 Complete Class

Overview

Quicksort is a simple sorting algorithm that works by choosing a certain element, called the pivot, and then dividing the list into two lists (a divide-and-conquer strategy), those items less than the pivot and those greater than or equal to the pivot. Each list is then recursively sorted.

In this Java implementation of Quicksort, the array to be sorted can be of any type that extends Comparable, making it usable with Java's referential numeric types like Float, Double, Integer, etc. as well as e.g. with Strings. The implementation therefore requires Java 5.

The elements to be swapped to ensure sorted partitions are searched in do-while loops, the elements in the array are sorted in ascending order.

Implementation

• This implementation sorts a given array of comparable elements in ascending order, as exemplified by the following test.

<<test_integer_body>>=
Integer[] array = { 5, 3, 4, 2, 1 };
quicksort(array);
Integer[] correct = { 1, 2, 3, 4, 5 };
assertArrayEquals(correct, array);

• The method we just called uses Java generics to allow all arrays of types that extend Comparable. This is formalised by describing a type that extends Comparable (T extends Comaprable) which itself is a supertype of T (? super T). The latter lower bounded wildcard allows implementing Comparable with a parameter (class Bar implements Comparable<Object>), since it ensures that the type T can not be compared to exactly T only, but to any instance of the supertype.

<<start_method>>=
static <T extends Comparable<? super T>> void quicksort(T[] array)

• Start conquering the array from the beginning (0) and from the end (array.length - 1), thereby dividing it into two partitions.

<<start>>=
quicksort(array, 0, array.length - 1);

• The recursive method we just called, using Java generics to allow all arrays of types that extend Comparable, as described above.

<<recursive_method>>=
static <T extends Comparable<? super T>> void quicksort(T[] array, int left0, int right0)

• First, let's initialize the local variables we use in that recursive method.

<<initialize>>=
int left = left0;
int right = right0 + 1;
T pivot, temp;

• This implementation uses the first element in the array as the pivot element, which results in Quicksort's worst case runtime behaviour of O(n²) for already sorted arrays. A practical implementation would probably use some other set_pivot function -- see Quicksort_(C_Plus_Plus)#Pivot_functions for pivot functions that work much better for already sorted arrays.

<<set_pivot>>=
pivot = array[left0];

• Search an element > pivot in the partition from left to right.

<<search_from_left>>=
do left++; while (left <= right0 && array[left].compareTo(pivot) < 0);

• Search an element < pivot in the partition from right to left.

<<search_from_right>>=
do right--; while (array[right].compareTo(pivot) > 0);

• At this point, we may have found two values that are out of order -- if so, swap them.

<<swap>>=
if (left < right) {
	temp = array[left];
	array[left] = array[right];
	array[right] = temp;
}

• Process the remaining interval step-by-step. When there is no longer an interval between the already sorted partitions, we have finished partitioning the list into the two sub-lists.

<<process>>=
do {
	search_from_left
	search_from_right
	swap
}
while (left <= right);

• Copy the smallest value to the beginning. Is this copy_smallest really necessary?

<<copy_smallest>>=
temp = array[left0];
array[left0] = array[right];
array[right] = temp;

• If the left partition has more than 1 element, recursively sort that sublist.
• If the right partition has more than 1 element, recursively sort that sublist.

<<recursion>>=
if (left0 < right) quicksort(array, left0, right);
if (left < right0) quicksort(array, left, right0);

Unit Tests

• To test the method, we first import the JUnit 4 test annotation and the static assertArrayEquals method.

<<import>>=
import static org.junit.Assert.assertArrayEquals;
import org.junit.Test;

• Test the sorting with Java's Integer type.

<<test_integer>>=
@Test
public void integerSorting() {
	test_integer_body
}

• Test the sorting with Java's Float type.

<<test_float>>=
@Test
public void floatSorting() {
	Float[] array = { 1.8F, 3.6F, 4F, 5F, 2F };
	quicksort(array);
	Float[] correct = { 1.8F, 2F, 3.6F, 4F, 5F };
	assertArrayEquals(correct, array);
}

• Test the sorting with Java's String type.

<<test_string>>=
@Test
public void stringSorting() {
    String[] array = {"Batman", "Spiderman", "Anthony", "Zoolander"};
    quicksort(array);
    String[] correct = {"Anthony", "Batman",  "Spiderman",  "Zoolander"};
    assertArrayEquals(correct, array);
}

Complete Class

• This results in the following class.

<<Quicksort.java>>=
import
public class Quicksort {
	start_method {
		start
	}
	recursive_method {
		initialize
		set_pivot
		process 
		copy_smallest
		recursion
	}
	test_integer
	test_float
	test_string
}

Download code