[4,6,3,7,5,1,2,9,8]. Then the following
steps will sort the list:
Step List 1 List2 1: [4,6,3,7,5,1,2,9,8] [] 2: [6,3,7,5,1,2,9,8] [4] 3: [3,7,5,1,2,9,8] [4,6] 4: [7,5,1,2,9,8] [3,4,6] 5: [5,1,2,9,8] [3,4,6,7] 6: [1,2,9,8] [3,4,5,6,7] 7: [2,9,8] [1,3,4,5,6,7] 8: [9,8] [1,2,3,4,5,6,7] 9: [8] [1,2,3,4,5,6,7,9] 10: [] [1,2,3,4,5,6,7,8,9]Here is some code which implements this sorting algorithm
public static LispList<Integer> sort(LispList<Integer> ls1)
// Sorting list ls1 using insertion sort
{
LispList<Integer> ls2 = LispList.empty();
for(;!ls1.isEmpty(); ls1=ls1.tail())
ls2 = insert(ls1.head(),ls2);
return ls2;
}
public static LispList<Integer> insert(Integer n,LispList<Integer> ls1)
// Insert an integer into an ordered list of integers
{
LispList<Integer> ls2 = LispList.empty();
for(;!ls1.isEmpty();ls1=ls1.tail())
{
Integer h=ls1.head();
if(h.compareTo(n)>0)
break;
ls2=ls2.cons(h);
}
ls1=ls1.cons(n);
for(;!ls2.isEmpty();ls2=ls2.tail())
{
Integer h=ls2.head();
ls1=ls1.cons(h);
}
return ls1;
}
This code can be found, together with supporting code to enable it
to be demonstrated, in the file
SortLispLists1.java
which you can obtain from the directory
~mmh/DCS128/code/lispLists.
The code for the method which inserts an item into an ordered list and keeps it ordered uses iteration with the "stack and reverse" technique we discussed previously. We take the items off the sorted list and stack them onto a temporary list until we come across one which is greater than the one we're inserting, then we know we've reached the right place to insert the new item. We then put the new item in its place, and take the items off the temporary list one by one and put them back on the sorted list, until the temporary list is emnpty. When we're unstacking from the sorted list, we may get down to the bottom of the list (that is, it becomes the empty list), which means that the item we're inserting is greater than any of the items that were in the list, so should be put at the bottom of the stack (that is, the end of the list) with the other items pushed back on top of it.
Note we use h.compareTo(n)>0 to see if h
holds a value greater than n. This is because h
and n are of type Integer, and you can
compare values of this type using compareTo, which you
previously saw used to compare
strings against each other in alphabetic ordering.
It would have been possible to have written the code for the method
sort in a single method, which would look like:
public static LispList<Integer> sort(LispList<Integer> ls1)
// Sorting list ls1 using insertion sort
{
LispList<Integer> ls2 = LispList.empty();
for(;!ls1.isEmpty(); ls1=ls1.tail())
{
Integer n = ls1.head();
LispList<Integer> ls3 = LispList.empty();
for(;!ls2.isEmpty();ls2=ls2.tail())
{
Integer h=ls2.head();
if(h.compareTo(n)>0)
break;
ls3=ls3.cons(h);
}
ls2=ls2.cons(n);
for(;!ls3.isEmpty();ls3=ls3.tail())
{
Integer h=ls3.head();
ls2=ls2.cons(h);
}
}
return ls2;
}
This code, which can be found in the file
SortLispLists2.java,
works just the same as the code previously given, but it is harder
for humans to look at the code and understand how it works. It often makes
sense when writing code to implement an algorithm to have separate
methods to implement steps in the algorithm. In this case, the action of
creating a list which represents inserting an integer in order into
an ordered list of integers is a separate step. Making a separate method
to do it makes the code easier for us to follow. We can look at the code
for method sort and see it involves repeated calls of the
method insert which does the insertion operation. It is
not so clear how the code breaks down into separate operations when it
is given as just one long method containing loops within a loop. When writing
code, it often makes sense to write code which call a method to perform
some operation, and only later to write the code for that method itself.
An alternative way of writing the insert method would be to
use recursion. Here is code where the problem is tackled in this way:
public static LispListYou can find this code in the file SortLispLists3.java. The idea is that if you insert an element into a list and it turns out the list is the empty list, all you have to do is put it at the front making a new list of just one element. Otherwise, you compare the item being inserted with the item at the front of the list. If the item at the front of the list is greater than the item being inserted, then to keep numerical order, the item being inserted should be put at the front of the list. If the item at the front of the list is less than the item being inserted, you insert that item into the rest ofthe list, then put the original front item at the front of the result. Inserting an item into the rest of the list is just a version of the problem of inserting an item into a list, so it can be solved by a recursive call.insert(Integer n,LispList ls1) // Inserting an integer into an ordered list, expressed recursively { if(ls1.isEmpty()) return LispList. empty().cons(n); Integer h = ls1.head(); if(h.compareTo(n)>0) return ls1.cons(n); else { LispList ls2 = insert(n,ls1.tail()); return ls2.cons(h); } }
The sort method can also be expressed recursively. If a
list is empty, then the sorted version of that list must be the
empty list. Otherwise, if you sort the tail of the list and then
insert its head item into the result, you must get a list which
consists of all the items from the original list in sorted order.
This is expressed by the following code:
public static LispList<Integer> sort(LispList<Integer> ls)
{
if(ls.isEmpty())
return LispList.empty();
else
return insert(ls.head(),sort(ls.tail()));
}
You can find this code in the file
SortLispLists4.java.
Here, insert(ls.head(),sort(ls.tail())) means that first
the value of ls.head() is found, then the value of
ls.tail(), then the value of sorting ls.tail
is found through the call sort(ls.tail()), then the values
of ls.head() and >sort(ls.tail()) are passed as
arguments to the insert method. Remember, in Java the
arguments to a method are fully evaluated (in left-to-right order)
and then evaluation of the method itself takes place. If an argument to
a method is itself a method call, then the arguments to that method
have to be evaluated first and so on.
We noted that it often makes sense to write code which uses a separate
method without at first being concerned about what is in the method.
So we can write code for sort making it use insert,
assuming the code for insert works and
without being concerned about how it works.
We can then write the code for insert separately, at this
point all we need to be concernd about is that it performs the operation
of inserting an item into an ordered list correctly.
With recursion, it is even easier, we can write code with a recursive
call, and assume the recursive call works. Then we don't have to write
any more code since the recursive call uses the code we have already
written. Although this can seem mysterious, what is actually
happening is that the mechanism of making the recursive call, establishing
a new environment for it, and then returning to the old environment
when the recursive call finishes, does a lot of book-keeping work for us
which we would otherwise have to program in.
The important thing with a recursive method is that there must
always be cases where when it is called it does not make a
recursive call. Such a case is called a base case. In our
recursive code for sort, the base case is when the list
we're sorting is the empty list. In our recursive code for
insert, there are two base cases. The first is when
the list we're inserting the item into is the empty list, the
second is when the item we're inserting is less than the first
item in the list we're inserting it into. In a recursive method,
any recursive call must have an argument which is closer to a
base case than the argument of the original call. In recursion with
lists, this will usually be through a list argument in the
recursive call being a shorter list than the original list argument.
Although we gave several ways of coding the algorithm above,
they are all really coding variations on the one algorithm
called insertion sort. There are many different algorithms
for sorting a list other than insertion sort, and we shall discuss
a different one below.
Quick sort on Lisp lists
The basis of the quick sort algorithm is as follows: you divide an
unsorted collection into two parts, all those items less than
a particular item (called the "pivot") and all those items greater than it.
Then you sort each part. Then you join the result of sorting the two parts
together with the particular item used to make the split in the
middle. The result is a sorted collection. Suppose, for example,
we want to sort the Lisp list [4,6,3,7,5,1,2,9,8].
We could break it into two parts, the list of all those
elements less than the first element (4) and the
list of all elements greater than the first element. This would
give us the two lists [3,1,2] and [6,7,5,9,8],
if we assumed the items in the lists were in the same order they
were in the original list. Sorting these two lists gives
[1,2,3] and [5,6,7,8,9]. Joining them
together with the original first item in the middle gives
[1,2,3,4,5,6,7,8,9], which is the original list
sorted.
The following code gives sorting of a Lisp list using quick sort:
public static LispList<Integer> sort(LispList<Integer> ls)
// Returns a list containing the elements of ls in numerical ascending order
// Sorts using quick sort.
{
if(ls.isEmpty()||ls.tail().isEmpty())
return ls;
Integer pivot = ls.head();
ls = ls.tail();
LispList<Integer> smaller = LispList.empty();
LispList<Integer> greater = LispList.empty();
for(; !ls.isEmpty(); ls=ls.tail())
{
Integer h = ls.head();
if(h.compareTo(pivot)<0)
smaller = smaller.cons(h);
else
greater = greater.cons(h);
}
smaller = sort(smaller);
greater = sort(greater);
greater = greater.cons(pivot);
return append(smaller,greater);
}
public static <T> LispList<T> append(LispList<T> ls1,LispList<T> ls2)
// Join ls1 to ls2
{
if(ls1.isEmpty())
return ls2;
else
{
T h = ls1.head();
LispList<T> ls3 = append(ls1.tail(),ls2);
return ls3.cons(h);
}
}
This code can be found in the file
SortLispLists5.java.
Here, the list of all items less than and all items greater than the
pivot is actually built in reverse since we do it using iteration and
it doesn't matter what order they come in. So here if the original
list referred to by the variable ls is
[4,6,3,7,5,1,2,9,8], when the for-loop finishes it
will result in the variable smaller referring to the list
[2,1,3] and the variable greater referring
to the list [8,9,5,7,6]. It is important to note that the
recursive calls sort(smaller) and sort(greater)
are calls to the same method. But remember that method calls
are evaluated in their own environment, as we noted
previously, and this
applies to recursive method calls just the same as any other method call.
So when the call sort(smaller) is made, it is executed in
a new environment where ls is a separate variable from
ls in the old environment, and ls in the
new environment refers to what smaller refers to in
the old environment. When this recursive call finishes, the assignment
smaller = sort(smaller) causes smaller
in the old environment to be assigned to stop referring to the unsorted
list it use to refer to and start referring to the sorted list passed
as the result of the recursive call.
The base case is when the list being sorted is empty or has just one element, in this case the list can be returned as it is. The two recursive calls will always be on a list of at least one less than the original list since the pivot is not included either of the lists passed as arguments to recursive calls. If it happened that all the items in the list were greater than the pivot, one recursive call would have the empty list as its argument, the other would have a list of length one less than the original list. So long as it can't be the case that a list of the same length as the original list is passed as the argument to the recursive call, a base case will always eventually be reached.
The code to join two lists is given by a separate method called
append. Since this method does not depend on the
contents of the list being of any particular type, it is written
as a generic method. Appending two lists together is best expressed
as a recursive operation because it can be defined naturally in
a recursive way. Appending the empty list to a list gives that same
list, for example appending [] to [4,5,6,7,8,9]
gives [4,5,6,7,8,9]. Appending a list which is not empty to
another list gives the same result as appending the tail of that
list to the other list, and then joining the head of that list to
the front of the result which can be done using cons.
For example, appending [1,2,3]
to [4,5,6,7,8,9] gives the same result as
appending [2,3] to [4,5,6,7,8,9], giving
[2,3,4,5,6,7,8,9] and then joining 1 to
the front to give [1,2,3,4,5,6,7,8,9]. Writing
recursive methods involves looking for patterns like this where
a call of the method on arguments which reduce the size of the
original problem give a solution which can be midified to give an
answer to the original problem.
A variation of quick sort avoids the use of an append operation.
Suppose we have a method sort such that the
call sort(ls1,ls2) gives the result of sorting
ls1 and appending the result to ls2.
Then suppose we divide ls1 into two lists as before,
s and g where s consists
of all those items from ls1 which are smaller than
the first item of ls1 and g gives all
those items of ls1 which are larger than the first
item. Following this, sort(g,ls2) using the same
definition of sort gives the result of sorting
all the items in g and joining them to ls2
in order. But if g1 is the result of joining
the first item of ls1 onto this, then
sort(s,g1) will give the result of sorting
s and joining the result to g1, and this
is the same as sorting ls1 and joining the result to
ls2. Now with this, the result of calling
sort(ls1,ls2) when ls2 is the empty
list is the same as just sorting ls1. So this
gives us the following code for a sort method:
public static LispList<Integer> sort(LispList<Integer> ls)
// Returns a list containing the elements of ls in numerical ascending order
// Sorts using quick sort onto an accumulator.
{
return sort(ls,LispList.<Integer>empty());
}
private static LispList<Integer> sort(LispList<Integer> ls1,LispList<Integer> ls2)
// Returns a list containing the elements of ls1 in numerical ascending order
// joined to ls2.
{
if(ls1.isEmpty())
return ls2;
Integer pivot = ls1.head();
ls1 = ls1.tail();
LispList<Integer> smaller = LispList.empty();
LispList<Integer> greater = LispList.empty();
for(; !ls1.isEmpty(); ls1=ls1.tail())
{
Integer h = ls1.head();
if(h.compareTo(pivot)<0)
smaller = smaller.cons(h);
else
greater = greater.cons(h);
}
greater = sort(greater,ls2);
return sort(smaller,greater.cons(pivot));
}
This code can be found in the file
SortLispLists6.java.
It demonstrates another way of going about solving problems - you
consider your problem to be a special version of some other problem,
and then write recursive code to solve that other problem. The recursive
code is given as a private method, since it is only for use internally
in the class, while the public method just makes a call to the private
method with the extra arguments as required.
Merge sort on Lisp lists
Merge sort works in a similar way to quick sort - the list is divided
into two parts, each part is sorted recursively, and then the two
sorted parts are combined together to make a sorted whole. However,
with quick sort, the task of comparing items in the list is done
during the division into two parts and before the recursive calls,
and the task of combining the two parts together after the recursive
calls involves no comparison. With merge sort it is the other
way round: the division into the two parts is simple involving
no comparisons, while the work of comparing items against each other
is done when the sorted lists are combined together.
The algorithm is to divide the initial list into two parts of roughly equal size. With linked lists this can be done by repeatedly taking two items off the front of the list, and putting one onto one new list and the other onto the other new list, until the whole list has been gone through. Then the two lists are sorted recursively, the base case of course being when the list being sorted is the empty list or has just one element. The resulting two sorted lists must be merged, hence the name of the sort algorithm. Merging involves taking whichever is the smallest of the front elements of the two sorted lists, and putting it on the front of the merger of the tail of the list it is taken off and the whole of the other list.
Using our example, sorting [4,6,3,7,5,1,2,9,8] first
involves the division into the two lists [8,2,5,3,4] and
[9,1,6,7]. You can see that these lists are the odd
positioned and even positioned items from the original list in
reverse order. Sorting these two lists gives
[2,3,4,5,8] and [1,6,7,9]. Now merging
them involves noting that the smallest item at the front of either
is 1. Taking this off leaves [2,3,4,5,8] and
[6,7,9]. Merging these two gives [2,3,4,5,6,7,8,9].
Putting the 1 at the front gives [1,2,3,4,5,6,7,8,9],
which is the answer we want.
The following code implements this:
pub1ic static LispList<Integer> sort(LispList<Integer> ls)
// Returns a list containing the elements of ls in numerical ascending order.
// Sorts using merge sort.
{
if(ls.isEmpty()||ls.tail().isEmpty())
return ls;
LispList<Integer> ls1 = LispList.empty();
LispList<Integer> ls2 = LispList.empty();
for(;!ls.isEmpty(); ls=ls.tail())
{
ls1 = ls1.cons(ls.head());
ls = ls.tail();
if(!ls.isEmpty())
ls2 = ls2.cons(ls.head());
else
break;
}
ls1 = sort(ls1);
ls2 = sort(ls2);
return merge(ls1,ls2);
}
public static LispList<Integer> merge(LispList<Integer> ls1,LispList<Integer> ls2)
{
if(ls1.isEmpty())
return ls2;
else if(ls2.isEmpty())
return ls1;
else
{
Integer h1 = ls1.head();
Integer h2 = ls2.head();
if(h1.compareTo(h2)<0)
{
LispList<Integer> ls3 = merge(ls1.tail(),ls2);
return ls3.cons(h1);
}
else
{
LispList<Integer> ls3 = merge(ls1,ls2.tail());
return ls3.cons(h2);
}
}
}
It can be found in the file
SortLispLists7.java.
You can see that merge takes two lists as its
arguments. The two base cases are when either of the lists
is empty, since the merger of any list with the empty list
must be that same list. The recursive call will always be
a step towards a base case since it will always be with
either one or the other list argument of one shorter length.
As before, you can see we have argued that the code works
not by tracing how one recursive call makes another recursive call
which makes a further recursive call, and so on, but just by showing
that if the recursive call works and there is a base case which works,
then the whole thing works. This uses a principle you may have come
across in mathematics as induction.
However, merging could be done using iteration rather than recursion, using the stack and reverse technique. In this case, we start with the two lists and a new list originally set to the empty list. We then take off from either of the two lists whichever has the lower top item, and put that item onto the new list. We do this until one of the lists is empty. Then the new list is the merger of the items taken off the two lists, but in reverse order. So we reverse them back again one by one onto whichever of the two original lists did not get completely emptied. Here is the code for this:
public static LispList<Integer> merge(LispList<Integer> ls1,LispList<Integer> ls2)
{
LispList<Integer> ls3 = LispList.empty();
while(!ls1.isEmpty()&&!ls2.isEmpty())
{
Integer h1 = ls1.head();
Integer h2 = ls2.head();
if(h1.compareTo(h2)<0)
{
ls3 = ls3.cons(h1);
ls1 = ls1.tail();
}
else
{
ls3 = ls3.cons(h2);
ls2 = ls2.tail();
}
}
if(!ls2.isEmpty())
ls1=ls2;
while(!ls3.isEmpty())
{
Integer h = ls3.head();
ls1 = ls1.cons(h);
ls3 = ls3.tail();
}
return ls1;
}
You may be interested to know that recursion, as it actually works in
practice, does the same thing, but with the mechanism for making new
environments and returning to old environments in effect creating
and reversing the merged list. Code for merge sort using this iterative
version of the merge method can be found in
SortLispLists8.java.
Last modified: 18 July 2005