In the last tutorial we looked at the bubble-sort algorithm. As was
mentioned, a major drawback of this algorithm is that it is slow and
impractical for applications where there is a lot of information to
be sorted. In this tutorial we will look at how the bubble-sort
algorithm can be refined to increase the speed of its sorts. As any programmer worth his salt will tell you, if you want to speed
up your routines then look at where it is spending most of its time
and try to reduce the amount of time spent there. Looking at the
algorithm for the bubble-sort we can see that a lot of time is spent
during each pass comparing list entries and, where necessary,
swapping them about. One solution for reducing the amount of time
spent in this process is known as the delayed replacement sort. The delayed replacement sort works in a similar manner to the
standard bubble-sort with the exception that no swaps are made until
after a pass is completed, hence why it is called a delayed
replacement sort. To illustrate how this is done let us have a look
at another list of numbers: 7 8 3 9 6 For an ascending sort the delayed replacement algorithm makes a pass
through the numbers looking for the lowest value (highest value if
it's a descending sort or alternatively you can start at the last
entry and work your way up). In the above example we can see that
the lowest value in the list is 3. The delayed replacement sort will
swap this number with the first number in the list so that we get the
following: 3 8 7 9 6 The algorithm will continue with another pass, only this time it will
look for the second lowest number, in this case the number 6. It
will then swap this with the number that is second in the list. This
gives us: 3 6 7 9 8 This process of looking for the next number up and swapping it with
the number occupying the appropriate space in the list will keep
going until it reaches the last entry in the list. Since only one swap is made per pass as opposed to numerous swaps in
the standard bubble-sort the amount of time spent during each pass is
greatly reduced. Here is the algorithm for the delayed replacement sort in pseudo-code:
The advantages of the delayed replacement sort are that it is
relatively easy to program and only requires a minimum amount of
memory. As already stated, it is faster than the conventional
bubble-sort (approx. 50% faster). Disadvantages of the delayed
replacement sort algorithm is that it is still pretty slow compared
with some of the other sort algorithms out there and not ideal if you
have a huge amount of data to sort. In the next instalment of this series of tutorials we will be
looking at a different type of sorting algorithm called the shell
sort. If you have any comments on this series of tutorials so far or would
like to see programming tutorials on other topics then please e-mail
me at fgloch@yahoo.com or write to:
Begin DELAYEDSORT
For ITEM=1 to maximum number of items in list-1
LOWEST=ITEM
For N=ITEM+1 to maximum number of items in list
Is entry at position N lower than entry at position LOWEST?
If so, LOWEST=N
Next N
Is ITEM different from LOWEST
If so, swap entry at LOWEST with entry in ITEM
Next ITEM
End DELAYEDSORT