# Quicksort (Java)

### 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 |

# 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<TextendsComparable<?superT>>voidquicksort(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<TextendsComparable<?superT>>voidquicksort(T[]array,intleft0,intright0)

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

<<initialize>>=intleft = left0;intright = 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*^{2}) 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>>=doleft++;while(left <= right0 && array[left].compareTo(pivot)< 0);

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

<<search_from_right>>=doright--;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>>=@TestpublicvoidintegerSorting(){test_integer_body}

- Test the sorting with Java's Float type.

<<test_float>>=@TestpublicvoidfloatSorting(){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>>=@TestpublicvoidstringSorting(){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>>=importpublicclassQuicksort{start_method{start}recursive_method{initialize set_pivot process copy_smallest recursion}test_integer test_float test_string}

Download code |