public static ArrayList<Integer> sort(ArrayList<Integer> a)
{
if(a.size()<=0)
return a;
ArrayList<Integer> smaller = new ArrayList<Integer>();
ArrayList<Integer> greater = new ArrayList<Integer>();
Integer pivot = a.get(0);
for(int i=1; i<a.size(); i++)
{
Integer n=a.get(i);
if(n.compareTo(pivot)<0)
smaller.add(n);
else
greater.add(n);
}
smaller=sort(smaller);
greater=sort(greater);
smaller.add(pivot);
smaller.addAll(greater);
return smaller;
}
You can find this code in the files
QuickSort1.java and
QuickSort2.java, the
first displaying the randomly generated numbers which are sorted,
the second giving only the timing figures. Note this relies on
arrayLists being flexible in size, since we do not know in advance
the number of items which are less than the first item. Note also
that it uses another method which is provided for us by Java's
code library, addAll. If a and b
refer to two arrayList objects, then the call a.addAll(b)
destructively changes the object referred to by a so
that all the items from the object referred to by b
are added to it, in the order they occurred, after the existing items.
If we wish to code constructive quick sort on arrays rather than arrayLists, we can do so by a simple trick. We go through the original array once to find the number of elements less than the pivot. This gives us the size of the array of elements less than the pivot, and by implication, the size of the array of elements greater than or equal to the pivot not including the pivot itself. So we create arrays of these sizes and go back through the original array putting its elements into one or other of the new arrays. We then sort these new arrays, and join the results together in a final array of the same size as the original array. This gives us the following code:
public static Integer[] sort(Integer[] a)
{
if(a.length==0)
return new Integer[0];
else if(a.length==1)
{
Integer[] b = new Integer[1];
b[0]=a[0];
return b;
}
else
{
Integer pivot = a[0];
int count=0;
for(int i=0; i<a.length; i++)
if(a[i].compareTo(pivot)<0)
count++;
Integer[] smaller = new Integer[count];
Integer[] greater = new Integer[a.length-count-1];
for(int i=1, j=0, k=0; i<a.length; i++)
if(a[i].compareTo(pivot)<0)
smaller[j++]=a[i];
else
greater[k++]=a[i];
smaller = sort(smaller);
greater = sort(greater);
Integer[] b = new Integer[a.length];
for(int i=0; i<count; i++)
b[i]=smaller[i];
b[count]=pivot;
for(int i=0; i<greater.length; i++)
b[count+i+1]=greater[i];
return b;
}
}
Note the code for the loop which goes through the original array
(referenced by variable name a) and copies references
to its items into either one or other of the new arrays (referenced
by variable names smaller and greater). This is
the loop:
for(int i=1, j=0, k=0; i<a.length; i++)
if(a[i].compareTo(pivot)<0)
smaller[j++]=a[i];
else
greater[k++]=a[i];
Here, i is the index to the original array,
j is the index to the array smaller and
k is the index to the array greater.
These three int variables are declared together in
the initialisation part of the loop, but only i is updated
in the update part of the loop. This is because each time round the loop
we need to consider the next item from the array a, but
we only update j if we add that item to the array
smaller and we only update k if we add
that item to the array greater. Remember that j++
means "use the value of j then increase it by 1". So
smaller[j++]=a[i] is equivalent to:
smaller[j]=a[i]; j=j+1;Be careful to recall this is different from:
j=j+1;
smaller[j]=a[i];
which is the equivalent of smaller[++j]=a[i], and remember
that the ++ operators change the value of an integer variable
permanently, so don't think that smaller[j++]=a[i] is the same
as smaller[j+1]=a[i] where there is nothing to change the
value of j.
You can find code for constructive quick sort of arrays of integers
in the form given here in the files
QuickSort3.java and
QuickSort4.java.
Quick Sort in Place
A simple way of obtaining destructive quick sort would be to copy the
elements from the two sorted arrays in the above code back into the original
array rather than into a new array, but otherwise use code similar to
the constructive quick sort given above. This would give the code:
public static void sort(Integer[] a)
{
if(a.length>1)
{
Integer pivot = a[0];
int count=0;
for(int i=0; i<a.length; i++)
if(a[i].compareTo(pivot)<0)
count++;
Integer[] smaller = new Integer[count];
Integer[] greater = new Integer[a.length-count-1];
for(int i=1, j=0, k=0; i<a.length; i++)
if(a[i].compareTo(pivot)<0)
smaller[j++]=a[i];
else
greater[k++]=a[i];
sort(smaller);
sort(greater);
for(int i=0; i<count; i++)
a[i]=smaller[i];
a[count]=pivot;
for(int i=0; i<greater.length; i++)
a[count+i+1]=greater[i];
}
}
and you can find this code in the files
QuickSort5.java and
QuickSort6.java.
Although this is destructive, since the array passed as an
argument is changed, it does involve the construction of
the two temporary arrays indexed by smaller and
greater, and when each of these are sorted further
temporary arrays are created as the algorithms is executed recursively.
Since it is destructive, new arrays are not created in the base case
when the array being sorted is of length 1 or 0.
However, there is another version of quick sort on arrays which does not involve any construction of new arrays. Instead it works just by swapping the items around in the array, as we saw previously with the destructive selection sort. This is referred to as quick sort in place
The algorithm is the same before: divide the array into two portions, one containing all the items less than the pivot, the other containing all the items greater than or equal to the pivot, then sort each of these two portions recursively. However, in this case instead of creating new arrays, we move the items about in the original array until they are in positions where one section of the array is smaller items and the other section is larger items. We do not know at the start how many items are less than the pivot and how many are greater, so the two sections are not necessarily equal in length. The base case is when the section being sorted has 0 or 1 items in it.
There are several variations on the way this can be coded, but they all work on the principle of starting with two indexes to the portion of the array being sorted, one indexing either end. The lower one is increased to index further up the array and the higher one is decreased to index lower down the array, until the lower one indexes an item greater than or equal to the pivot and the upper one indexes an item less than the pivot. These two items are then swapped in position. This is repeated until the two indexes have crossed over. At that point, the array has been partioned into a smaller and larger section, and these sections are sorted recursively.
Here is some code to do this:
public static void sort(Integer[] a)
{
sort(a,0,a.length);
}
private static void sort(Integer[] a,int from,int to)
{
if(to>from+1)
{
Integer pivot = a[from];
int low=from+1,high=to-1;
while(low<high)
{
while(low<high&&a[low].compareTo(pivot)<0)
low++;
while(pivot.compareTo(a[high])<0)
high--;
if(low<high)
{
swap(a,high,low);
low++;
high--;
}
}
while(pivot.compareTo(a[high])<0)
high--;
swap(a,from,high);
sort(a,from,high);
sort(a,high+1,to);
}
}
private static void swap(Integer[] a,int pos1,int pos2)
{
Integer temp = a[pos1];
a[pos1]=a[pos2];
a[pos2]=temp;
}
In this version, the first item in the section of the array being sorted is
used as the pivot. Once the high index has crossed with
the low index it may need to be moved down further until
it indexes an item less than or equal to the pivot, which thus must be
the last item in the smaller valued section of the array. This item is
swapped with the pivot item, so the pivot item is positioned between the smaller
items and the larger items. When the recursive sorts are finished, the whole
array will then be sorted.
The work of the sorting is done in the method sort
which takes three arguments, a reference to the array, the position of the
first item in the section of the array which is currently being sorted,
and the position following the position of the last item in the section of
the array being sorted. Initially this method is called with the two positions
being0 and the length of the whole array. So note that instead
of actually creating separate arrays to sort using a recursive method, we
have a method which sorts a section of one array, and recursive calls
sort smaller sections of the same array.
Let us consider an example. Suppose the whole array being sorted is
[30,25,47,99,8,12,28,63,16,20]Then we take
30 as the pivot, and start with the
low index at 1 and the high index at
9 (the index of the last component of the array).
Then the low index is increased until it has the value 2
which indexes 47 which is greater than 30,
and the high index remains at 9 as this indexes
the value 20, which is less than 30. Swapping
47 with 20 gives:
[30,25,20,99,8,12,28,63,16,47] low=2 high=9The
low index is increased by one and indexes the number
99 which is greater than 30. The high
index is decreased by one and indexes the number 16 which is less
than 30. These two numbers are swapped round giving:
[30,25,20,16,8,12,28,63,99,47] low=3 high=8
Now low is increased until it indexes the next item which
is greater than the pivot, which is 63 at position 7
while high is decreased until it indexes the next item which
is less than the pivot, which is 28 at position 6.
At this point, high and low have crossed over.
[30,25,20,16,8,12,28,63,99,47] low=7 high=6
Swapping the pivot with the item indexed by high gives:
[28,25,20,16,8,12,30,63,99,47]
We can now recursively sort the portion of the array [28,25,20,16,8,12]
and the portion [63,99,47]. But there is no need to copy the
numbers into separate arrays to do this, we just call the sort
method with the whole array, 0 and 6 as its
arguments to sort the first part, and with the whole array, 7 and
10 to sort the second part. When both parts are sorted, the
whole array is sorted.
Code for this version of quick sort can be found in the files
QuickSort7.java and
QuickSort8.java.
Code using the same algorithm, but applied to an arrayList rather
than an array can be found in the files
QuickSort9.java and
QuickSort10.java.
Merge Sort of arrays
The merge sort algorithm, which we saw
previously with
Lisp lists can also be applied to arrays. Unlike quick sort, however,
merge sort cannot be done completely in place, it always needs the
creation of temporary arrays. Since merge sort works by dividing the
original array into two equally sized halves, we can create these half
sized arrays immediately and sort them (note they will differ in size by
one if the original array is of odd length). It does not matter which items
go into each half, since in merge sort the work of comparing items is
done after the recursive calls when the sorted collections are merged.
Here is code for merge sort of an array of integers:
public static void sort(Integer[] a)
{
if(a.length>1)
{
int i,mid = a.length/2;
Integer[] half1 = new Integer[mid];
Integer[] half2 = new Integer[a.length-mid];
for(i=0; i<mid; i++)
half1[i]=a[i];
for(; i<a.length; i++)
half2[i-mid]=a[i];
sort(half1);
sort(half2);
int j=0, k=0;
for(i=0; j<half1.length&&k<half2.length; i++)
if(half1[j].compareTo(half2[k])<0)
{
a[i]=half1[j];
j++;
}
else
{
a[i]=half2[k];
k++;
}
for(; j<half1.length; i++, j++)
a[i]=half1[j];
for(; k<half2.length; i++, k++)
a[i]=half2[k];
}
}
The code before the recursive calls
sort(half1);
sort(half2);
creates two new arrays, and then copies the items from the first
half of the original array into one of them, and copies the items
from the second half into the other. The recursive calls apply the
same algorithm on these two arrays. The base case is when the array is of
length 0 or 1, so as the recursive calls are guaranteed to be on arrays
of smaller size than the original array, the base case will eventually be
reached.
The code after the recursive calls
merges the two sorted temporary arrays, referred to by variables
half1 and half2, back into the space of
the original array referred to by variable a. It uses
the technique we saw with partioning in constructive quick sort
of an index for each of the individual arrays, again with the
names i for the main array and j and k
for the smaller arrays. Again, i is increased each time
round the loop, and either j or k as
appropriate, but not both, is increased each time round the loop.
The merge part looks at the item in the array half1
indexed by j and the item in the array half2
indexed by k. It copies whichever of them is smaller
into a[i] and increases the index of whichever array
it was copied to by one, so next time round the loop the following
item in the array is looked at.
We can consider how this algorithm works on the array we used before,
[30,25,47,99,8,12,28,63,16,20]. It is divided into two halves,
[30,25,47,99,8] and [12,28,63,16,20].
Sorting these gives [8,25,30,47,99] and
[12,16,20,28,63]. Now let us consider merging them. We have:
[_,_,_,_,_,_,_,_,_,_] i=0 [8,25,30,47,99] j=0 [12,16,20,28,63] k=0
The first array here actually still stores the numbers in their original
order, but that is irrelevant as they will be overwritten in the
merger. Here, starting off with i, j and
k all at 0, half1[j] is 8
and half2[k] is 12, so half1[j]
is the lower, it is copied into a[i] and j
is increased by one, giving:
[8,_,_,_,_,_,_,_,_,_] i=1 [8,25,30,47,99] j=1 [12,16,20,28,63] k=0
Now half2[k] is lower than half1[j] so it
is copied into a[i] and k is increased by one
giving:
[8,12,_,_,_,_,_,_,_,_] i=2 [8,25,30,47,99] j=1 [12,16,20,28,63] k=1
And now half2[k] is lower than half1[j] again,
so it is copied into a[i] and k is
increased by one again, giving:
[8,12,16,_,_,_,_,_,_,_] i=3 [8,25,30,47,99] j=1 [12,16,20,28,63] k=2
Once again, half2[k] is lower than half1[j],
so the situation becomes:
[8,12,16,20,_,_,_,_,_,_] i=4 [8,25,30,47,99] j=1 [12,16,20,28,63] k=3
But now half1[j] is lower than half2[k], so
the situation becomes:
[8,12,16,20,25,_,_,_,_,_] i=5 [8,25,30,47,99] j=2 [12,16,20,28,63] k=3
You can see that by carrying on this work, the original array will
be filled with the items from the other two arrays in sorted order.
Actually, it won't quite work like this, it will always be the case that
j reaches the length of half1 when k
hasn't reached the length of half2, or the other way round.
Once the all the items from one of the arrays have been copied into the
original array, any items left in the other array have to be copied in
after them, that is why we have the additional statements:
for(; j<half1.length; i++, j++)
a[i]=half1[j];
for(; k<half2.length; i++, k++)
a[i]=half2[k];
The body in one or other of these loops will be executed, depending on
whether j is less than half1.length
or k is less than half2.length, to copy
the remaining items into the original array. The other loop will
only get as far as the loop test which will be false before the body
is executed.
Code for merge sort of arrays of integers, together with support code
to give your own integers, generate and print random integers, or
generate random integers and sort them but just give timing figures
can be found in the files
MergeSort1.java,
MergeSort3.java and
MergeSort5.java.
There is also code, with similar supporting code, to merge sort
arrays of strings in the files
MergeSort2.java,
MergeSort4.java and
MergeSort6.java.
You will need the file
WordGen.java to
generate random strings.
Merge sort can be applied to arrayLists as well as to arrays. The files
MergeSort7.java and
MergeSort8.java show
merge sort applied to arrayLists.
Note the merge sort code we have given here is destructive, because the
merger puts the sorted objects back into the same array or arrayList object
they came from originally. If they were instead put into a new array or
arrayList, we would obtain constructive merge sort.
Java's sorting methods
Sorting is such a fundamental task in computing that anyone who deserves
the description "Computer Scientist" ought to have a good familiarity with
the main sorting algorithms. It also helps us develop an understanding
of algorithms and of how code translates algorithms into something the
computer can obey to see these sorting algorithms and to see Java code
for them. However, in practice as a Java programmer you would not have
to write your own code to sort arrays of data. It is such a common
operation that the Java library provides code for you which does the job.
Not only does this mean you don't have to write your own code, you can
also be sure that the developers of the Java language put a lot of thought
into the code library they distribute with it. You can therefore be sure
that the array sorting methods they provide do not contain any errors
and are written to be the most efficient algorithm for sorting.
The philosophy of the Java language is to re-use code wherever possible.
So it's always a good idea to see if the Java language already supplies
code in its code library to fill a need you have, rather than write code
yourself. Note that it is not impossible for code supplied from elsewhere
to be error free. It is however much more likely to be error free than
code you have written yourself, in particular if you are using it in
a standard way to do standard tasks. As a novice programmer, you can safely
assume that the Java compiler and Java library code will always
work correctly - if your code does not work, it will be because of an
error or a misassumption you have made, not because of an error in
the compiler of library code.
The Java class Arrays in the package java.util
contains a range of static methods for doing common array operations.
It has a static method called sort which destructively
sorts arrays of any objects. So Arrays.sort(a) where
a refers to an array will change the array that a
refers to so that it is sorted. Note that the sorting it does is in the
order given by the compareTo method of the objects it
is sorting. For example, if str1 and str2 are
of type String then str1.compareTo(str2)
gives a negative number if str1 comes before str2
alphabetically, and a positive number if str1 comes
after str2 alphabetically. This means that if a
is of type String[] then Arrays.sort(a)
will sort the array referred to by a into alphabetical
order. This is not the only possible ordering you might want to apply
to an array of strings. For example, you might want to sort an array of
strings in order of their length rather than alphabetically. We will see
later how code for sorting can be generalised to allow different orderings
to be specified. The ordering given by an object's compareTo
methods is referred to as the natural ordering.
Even with an array of integers, while you might think the only possible
ordering you would ever need is the natural ordering of ascending
numerical order, there could be other possibilities, apart from
the obvious descending numerical order. Suppose, for example, you were
running a competition "guess the number of marbles in a jar", and you
knew the answer was 1037. Then if you had guesses stored in an array,
you would want to order those guesses in the order "closest to 1037".
In this ordering, 1042 comes before 1027, but after 1039. Again, this
illustrates the importance of being precise in your specification. What
you assume is the only possible interpretaton of some vaguely worded
specification such as "sort this array" may not be the only possible
one. It is always good to write specifications for code that has to be
written in such a way as there cannot possibly be any alternative
way of interpreting the specification.
In the files
JavaSort1.java and
JavaSort3.java, you
will find code that uses Java's sort method to
sort an array of randomly generated integers, in the first case
displaying the integers before and after sorting, in the second
displaying only timing figures. In the files
JavaSort2.java and
JavaSort4.java, you
will find code that uses Java's sort method to
sort an array of randomly generated strings (using the file
WordGen.java to
generate them). The strings are sorted in their default order,
which is alphabetical.
The Java class Collections is equivalent to the Java
class Arrays but dealing with arrayLists rather than
arrays. Actually, it deals with a range of Collection
types, of which ArrayList is just one example, but it
is the only example we have seen so far. So if a is
a variable of type ArrayList<Integer> or
ArrayList<String>, or an arrayList of any other
base type so long as that base type may have the method
compareTo called on it, then Collections.sort(a)
will re-order the contents of the arrayList referred to by a
according to the ordering given by the compareTo method
of the base type.
In the files
JavaSort5.java and
JavaSort7.java, you
will find code that uses Java's sort method to
sort an arrayList of randomly generated integers, in the first case
displaying the integers before and after sorting, in the second
displaying only timing figures. In the files
JavaSort6.java and
JavaSort8.java, you
will find code that uses Java's sort method to
sort an arrayList of randomly generated strings.
Matthew Huntbach
Last modified: 24 February 2006