Sorting
This document examines a collection of sorting Algorithms and compares
their relative efficiencies. Before we get started, however, we need some
definitions of what we mean by the term sorted data. Throughout
this document, the data is sorted in ascending order (the same as
a dictionary or telephone book). Everything that is said about data sorted
in ascending order applies equally to data sorted in descending order
as well. So, we have a list or array of data items (xi) such
that xi < xi+1 . After reading through this document,
you can proceed to the next page which allows you to run each of the algorithms
described. In doing this, you'll be able to experience first hand how the
different algorithms work and compare their relative efficiencies.
Interlude - Comparisons
Before we actually get started, it is necessary to look at how computers
compare data items as opposed to how you or I might do the same.
If we humans look at a small set of objects we are able to visually compare
them all and locate the smallest (or largest) one without conscious effort.
Computers, on the other hand are somewhat more limited! In general,
a computer can only examine two things at once. Thus we can find
which is the smaller of (1,2) but not (1,2,3) which is a problem too complex
for the average computer to solve in one step. All of the algorithms
presented below make use of this two-at-a-time comparison.
Bubblesort
The first sorting algorithm we'll look at is not that immediately obvious
to everyone at first. This algorithm assumes we can look at each pair of
values in our array at a time. If the pair is (xi, xi+1)
then if xi+1 < xi we swap (interchange) xi
and xi+1. This will sort two values, e.g. (4, 2) will become
(2,4). But what about (4,2,3)? To sort this list we need to apply the technique
repeatedly. First we'll swap the 4 and the 2 as before: (2, 4, 3) and then
we need to work on the next pair (4, 3) which we'll also swap: (2, 3, 4).
There, that's sorted! So our algorithm requires us to repeatedly apply
it - but for how long? Look at this: sort (4, 3, 2). This if we do the
sorting twice (as we did above) we get: (3, 2, 4) which isn't right. In
fact, we need to apply the algorithm until we do no more swaps. If we have
done no more swaps then it follows that (xi < xi+1)
for all i. Recall that this is the definition of a sorted list!
Bubblesort is a useful algorithm to look at because it is clear that
when the algorithm terminates, the list is sorted. The trouble with bubblesort
is that it is very inefficient. The efficiency of the algorithm is a measure
of how much work it does. In the case of bubblesort, there are two kinds
of work being done: comparing (xi with xi+1) and
swapping (if needed). If we have a list of length n to sort, Bubblesort
takes approximately n2 comparisons to complete. We can do better!
Selection Sort
Selection sort is a much more efficient algorithm than BubbleSort and is
just about as easy to describe. In this algorithm we scan through our list
looking for the smallest item. We then exchange the smallest item with
the one at the start of the list. We now repeat this process looking for
the second smallest item and swap that with the one in the second position
and so on. Looking at the process in another way, after k steps
in the algorithm we have two lists: one of length k of sorted items
and one of length n-k of un-sorted items. Just by looking
at the process in this way we can see that it has two nice properties:
-
It needs at most n-1 applications to terminate, and,
-
It does indeed sort the data
| A question to ask: how efficient is the algorithm? Well, at step k
of the algorithm, it has n-k items in the un-sorted part of the
list, so it will need to do n-k comparisons to find the smallest
item in the un-sorted part. So the answer must be : |
 |
|
|
Other Sorting Strategies
There are many different sorting algorithms, some of them are available
here as demonstrations and most books on Data Structures + Algorithms have
quite a number to chose from. So why are there so many and why wouldn't
you just use the fastest algorithm all the time? There are a number
of reasons why we might even use an algorithm like Bubble sort! Consider
the case when you know that the data you wish to sort is almost
always already sorted. If the data is already sorted, Bubble
sort will make 1 pass over the data, perform no swaps and terminate. Selection
sort on the other hand will carry on regardless. Clearly, in
this case the programmer will need to look at the relative probabilities
of the collection being already sorted and make the appropriate design
decision. Likewise, some algorithms which are very fast at sorting
data which is randomly distributed perform very badly if the data is reversed
(i.e. the data is in descending order and we want it in ascending order).
In addition to these points is the problem that some of the faster (and
more complex) algorithms have a fixed overhead. This means that
a certain amount of work must be done by the algorithm irrespective of
the number of items that are to be sorted. If we wish to use one of these
algorithms, we must make sure that the number of items to be sorted is
large enough, otherwise the cost of the algorithm is dominated by the fixed
overhead. As a rough, working rule-of-thumb, if the data set is of size
50 or so you will probably see a speed improvement and could sensibly choose
an algorithm like Quick sort.
Another issue which greatly affects algorithm choice is the size
of the data set we wish to sort. Both Selection and Bubble sort assume
we can hold the data in the computer's memory. But what if we can't? Computer
memories are getting larger all the time, but there are very large
data sets that some people use which will probably never fit in
the memory of any imaginable computer. To sort really huge data sets like
these we need to use a very different approach - the algorithms used to
do this kind of sorting are generally called merge-sorts and aren't covered
in this document. The algorithms which follow are just an indication of
some of the many available.
Quick Sort
This is not a very obvious algorithm at all. It is the result of the divide-and-conquer
approach. The algorithm first partitions the list into two parts such that
all of the elements in the first part are less than all of the elements
in the second part (this is much like Selection sort, described earlier).
It then repeats the partitioning in each of the two parts, continuing in
this way until it has a sequence of small partitions in which every element
in each partition is less than all of the elements in the next partition.
Then, another sort algorithm is used to finish putting the elements in
order. We could use Bubblesort or Selectionsort for example. The algorithm
achieves high efficiency because the partitioning step is very fast and
usually breaks its input into two parts of roughly equal size, and because
the simple sort algorithm works in roughly linear time on the type of input
that quicksort presents to it (i.e. pre-sorted chunks).
Shell Sort
This algorithm is named after its inventor and has nothing to do with Shells!
The algorithm works by simply striding through the array in large steps.
This algorithm is not very widely used and difficult to describe. It basically
strides though the array with a stride of 1/3 of the array size and uses
a selection sort to locate the smallest element. The stride is then reduced
by one and the process repeated until the stride is one and then the array
will be sorted. Analysing shell sort isn't very easy either but it
is faster than selection sort!
Click Here to run the sorting algorithms.