Pick out one item from the data, which is called
the pivot
Divide the collection into two collections, one all those items less
than
the pivot acording to the odering you are using, the other all those
items
greater than it
Sort the two collections (recursively, the base case being that if a
collection is empty, it is already sorted) into two ordered collections
Append the two ordered collections with the pivot in between them
Now we have a completely ordered collection containing the same
elements
as the original
For example, suppose we want to sort the list [14,12,9,17,22,20,8,6,25,5,3]. We choose the first element of this list, 14 as the pivot and divide it into two lists, one of all those elements less than 14, the other all those greater than 14, so we have [12,9,8,6,5,3] and [17,22,20,25]. We then sort both of those lists, giving us [3,5,6,8,9,12] and [17,20,22,25]. We then join them together, with 14 in the middle, giving us [3,5,6,8,9,12,17,20,22,25].
Quick sort is rather complicated when done with arrays, since we don't know in advance how many elements will be less than the pivot and how many greater. It can be done, however, and you can see code for it in many algorithms and data structures text books. It was in order to avoid this complexity, however, that in this course we covered merge sort as an example of an O(n log n) sorting algorithm rather than quick sort, which is also O(n log n).
With merge sort we know the size of the two collections we are dividing the original into will be half the size of the original. With quick sort this is not necessarily the case, in our example above the list was divided into two lists, one of length 6 the other of length 4, not two of length 5. In merge sort, most of the work of sorting, the comparison of elements is done after the recursive calls when the two sorted collections are merged. With quick sort the comparisons are done before the recursive calls as the collection is divided into two parts.
Quick sort is most efficient when the division (or "partition" as it is usually called) divides the collection into two roughly equal parts. If it happened that the number we chose as the pivot when sorting collection of integers into ascending order was the smallest number in the collection, our partition would be into two collections, one empty, and the other only one less in size than the original collection. For this reason, although the first number in a collection is often chosen as the pivot, this is a bad choice if the collection is ordered, and in some versions of quick sort a more elaborate choice of pivot is made.
Quick sort is easy to code when we are dealing with lists. Below is
a method for sorting a list of integers using quick sort, together
with a main method for demonstrating it:
import java.io.*;Here we use two separate methods to partition the original list, one gives a list of all elements less than or equal (this accounts for duplicates of the pivot) than the pivot, the other a list of all elements greater than the pivot. It would be preferable to have one method which just went through the list once returning both lists, but a Java method can only return one value.
class UseLists2
{
public static void main(String[] args)
throws IOException
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String str;
List l1, l2;
System.out.println("Enter a list: ");
str = in.readLine();
l1 = List.fromString(str);
l2 = quickSort(l1);
System.out.println("Sorting the list gives: ");
System.out.println(l2);
}
public static List append(List l1,List l2)
{
if(l1.isEmpty())
return l2;
else
return append(l1.tail(),l2).cons(l1.head());
}
public static List greaterThan(int n,List l)
{
if(l.isEmpty())
return List.empty();
else
{
int h = l.head();
List r = greaterThan(n,l.tail());
if(h>n)
return r.cons(h);
else
return r;
}
}
public static List lessThanOrEq(int n,List l)
{
if(l.isEmpty())
return List.empty();
else
{
int h = l.head();
List r = lessThanOrEq(n,l.tail());
if(h<=n)
return r.cons(h);
else
return r;
}
}
public static List quickSort(List l)
{
if(l.isEmpty())
return List.empty();
else
{
int p = l.head();
List t = l.tail();
List s = quickSort(lessThanOrEq(p,t));
List g = quickSort(greaterThan(p,t));
return append(s,g.cons(p));
}
}
}
quickSort
rather than as a separate method. Also the ordering of the two lists
the original is divided into doesn't matter, so we could use iteration
and end up with them in the reverse of their original order without
that affecting the result. Iteration is more efficient than recursion
because it doesn't involve the extra work of arranging for method
calls.
Another improvement we can make on our quick
sort algorithm removes
the use of the append method. This uses an idea known
as
concatenation elimination described by the computer scientist
Phil Wadler.
The idea was developed in the context of functional programming.
The introduction of the abstract data type List enables
us
to program in the Java language in a style which resembles functional
programming.
When we quicksort two lists and use append to join them together, we
have to run right through the first list to its end to join it to the
second. With our constructive lists, appending the first to the second
actually involves copying the entire first list. However, if we joined
the sorted version of the first list to the sorted version of the
second
list as we constructed it, we wouldn't have to append it afterwards.
So we use a variation of quick sort which takes two parameters,
l and acc and returns the sort of l
appended onto acc. Just to quicksort a list, we call
this with acc set to the empty list.
Below is the more efficient quickSort with the
partition
of the list done by iteration as part of the quickSort
method
rather than by recursion in a separate method, and using Wadler's
variation
of quicksort. There is also a main method to enable it
to be demonstrated, but of course it is no different from the main
method before.
import java.io.*;
class UseLists3
{
public static void main(String[] args)
throws IOException
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String str;
List l1, l2;
System.out.println("Enter a list: ");
str = in.readLine();
l1 = List.fromString(str);
l2 = quickSort(l1);
System.out.println("Sorting the list gives: ");
System.out.println(l2);
}
public static List quickSort(List l)
{
return quickSort(l,List.empty());
}
private static List quickSort(List l,List acc)
{
if(l.isEmpty())
return acc;
else
{
int p = l.head();
List s = List.empty();
List g = List.empty();
for(l=l.tail();!l.isEmpty();l=l.tail())
{
int h = l.head();
if(h>p)
g=g.cons(h);
else
s=s.cons(h);
}
l = quickSort(g,acc);
return quickSort(s,l.cons(p));
}
}
}
We can make this even more efficient by noting that we now have a
method
which is tail recursive,
that is the value it returns is given directly by a recursive call. We
can transform tail recursive methods into iterative methods, and doing
this on the above quickSort method gives us:
private static List quickSort(List l,List acc)The method is still recursive, because the original method had two recursive calls. Now, however, there is only one recursive call because the second one has been transformed into iteration. The cost of increasing the efficiency of the program is that the code is no longer so easy to understand. Our initial code for quick sort was almost a direct translation of the algorithm to code, so that once you are happy with recursion you do not have to do anything more to convince yourself it will work. Our final code is not nearly so clear.
{
while(!l.isEmpty())
{
int p = l.head();
List s = List.empty();
List g = List.empty();
for(l=l.tail();!l.isEmpty();l=l.tail())
{
int h = l.head();
if(h>p)
g=g.cons(h);
else
s=s.cons(h);
}
acc = quickSort(g,acc).cons(p);
l = s;
}
return acc;
}
}
Last modified: 11 March 2005