I recently posted this message in a Usenet newsgroup. I'm re-posting it
here just in case anyone is interested...
........
The topic of re-sorting is one that is often overlooked in the general
context of choosing sort algorithms. Many methods exist that are
wonderfully good at sorting long, randomly-jumbled lists of things. Of
course, they will also work if they are used to re-sort lists that have
previously been sorted, but to which one or a few additions or changes
have been made, so just a few items are out of their correct positions.
However, the algorithms that are optimized for dealing with randomized
lists are not the best for re-sorting. To re-sort a list that is already
nearly in order - which is a very common requirement in practice - a
version of the lowly "bubble sort" is vastly faster than more elaborate
algorithms such as shellsort, quicksort, and so on.
Here is some simple BASIC code that can be used to re-sort an array very
quickly:
-------------------start of code-----------------
 Start = FirstItem               'first item to be sorted, normally 1
 LastFound = LastItem            'last item to be sorted, normally N
 Direction = 1
 DO WHILE SGN(LastFound - Start) = Direction
   Finish = Start
   Start = LastFound - Direction
   Direction = - Direction
   FOR Pointer = Start TO Finish STEP Direction
      IF Item(Pointer) > Item(Pointer + 1) THEN
         SWAP Item(Pointer), Item(Pointer + 1)
         LastFound = Pointer
      END IF
   NEXT Pointer
 LOOP
-----------------end of code-------------------
The variables Start, Finish, Direction, LastFound, Pointer, FirstItem
and LastItem should all be declared as integers. The Item() array, which
is being sorted, can be of any type. The values of FirstItem and
LastItem must be fed into the routine at the start, along with the
initial (incompletely sorted) contents of the Item() array.
There are important differences between this version of the bubble sort
and the simplest version which almost everyone knows. Although the
FOR...NEXT loop is clearly what would be expected in a bubble sort, it
is executed alternately in opposite directions - specified by the
variable Direction, which alternates in value between 1 and -1. This
makes the sort more symmetrical than the conventional bubble sort, which
is much more efficient at moving a misplaced item in one direction
through the array than in the other. This alternating-direction or
"zigzag" bubble sort moves items efficiently in both directions.
The use of the variable LastFound serves two important purposes. First,
it allows the sort to identify parts of the array, at the beginning
and/or the end, where the items are already properly placed, so no SWAPs
occur there. These parts are omitted from subsequent iterations through
the FOR...NEXT loop. Second, LastFound effectively acts to terminate the
sort as soon as all the items are in order. Both of these functions help
the sort to execute in minimum time.
Of course, although the coding given above is to sort an array, the
algorithm can easily be used to sort a disk file. It can also be
transposed into different programming languages.
If you have a program that re-sorts a list of things, try using this
method. If you have previously been using a fancy algorithm that is good
for randomized lists, you will probably be very surprised by how much
better this is!
Incidentally, has anyone seen a "zigzag" bubble sort elsewhere? I have
been using this method for years, but have never noticed it anywhere
else.
                                    dow
---------------