This article was originally published in issue 20 of The Crypt Mag

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:

   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

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.

Article copyright © 2001, 2009 Francis G. Loch