Im Magazin „Computer Language" wurde in der Ausgabe September 1984 der folgende Artikel abgedruckt.
Ein grundlegender Artikel über verschiedene Sortierverfahren. Er enthält Beispiele in PASCAL

Bubble Sort,
Insertion Sort,
and Quicksort

Compared

Choosing the right sorting algorithm for the right task. By Richard G. Larson

Sorting data is an important use for ccomputers. It is also a valuable tool in developing other applications. But selecting a sorting algorithm that will perform best for a given job can be difficult since no algorithm is appropriate in every situation. Let's look at three popular sorting algorithms — Bubble Sort, Insertion Sort, and Quicksort — and consider their relative strengths and weaknesses.
Finding data in a sorted table is an obvious case where a sorting algorithm is needed. Think how much harder it would be, for example, to find a name in the telephone book if the names were not listed alphabetically. Sorting is often used to maintain symbol tables for compilers and assemblers. (Several years ago I wrote a cross assembler which assembled Z80 code on an IBM/370. By changing the algorithm that I used to sort the symbol table, I almost doubled its speed on large assemblies.)
Another example — suppose you wanted to find all duplicates in a list of 10,000 numbers. You could do this by comparing each number with all the numbers following it in the list, but this would involve approximately 50 million comparisons. Alternatively, if you could efficiently sort the numbers into increasing order, you could find duplicates by doing the 9,999 comparisons needed to compare each number with the number immediately following it.
Bubble Sort is probably the most popular sorting algorithm among computer hobbyists. This is unfortunate. Although there is no "best" sorting algorithm, many experts believe that Bubble Sort is a leading candidate for being the worst.
Basically, Bubble Sort works by going through the array being sorted and comparing adjacent elements. If two adjacent elements are in the wrong order, they are exchanged. By passing through the array repeatedly in this manner Bubble Sort eventually gets all pairs of elements in the correct order — at which point the array is finally sorted.
An examination of what happens to individual elements shows the reason for the name Bubble Sort. On the first pass through the data, a succession of exchanges causes the largest clement to "bubble up" to its final position. On the second pass, the next largest element bubbles up to its final position, and so forth.
One possible improvement in Bubble Sort involves keeping track of the location of the last out-of-order pair that was exchanged. Any data beyond this point must be in its final position and need not be examined again. In Listing 1 (printed here and also available on the COMPUTER LANGUAGE bulletin board service remote CP/M computer: (415) 957-9370, see disk file SORT1.LTG), the variable LastSwap is used to record this location. It also is used to record whether or not the data is already in order. LastSwap is initialized to before each execution of the inner loop. If it is still after the execution of the inner loop, then there were no exchanges and the data is sorted.
It can be shown that the average number of comparisons done by BubbleSort on randomly ordered data is approximately n2/2, where n is the number of elements.
Bubble Sort is a relatively inefficient sorting algorithm. When sorting large arrays, a lot of sorting algorithms are many times more efficient.
For sorting small arrays, Insertion Sort is significantly faster and somewhat simpler. One of the simplest sorting algorithms available, it works by repeating the following for j running from 2 through n: (Assume X[1] through X[j-1] are in sorted order.) Take X[j] and successively compare it with X[j-1], X[j-2] while moving each element larger than Xj] over one position. When the first X[i] is found that is not larger than X[j], insert X[j] immediately following it.
A standard modification (see Listing 2, also on the bulletin board service computer as disk file SORT2.LTG) is to put a dummy data element at X[0] that is known to be smaller than X[1] through X[n]. This eliminates the need for testing in the inner loop whether the loop index has reached the beginning of the array; even if it has, it will always stop when it encounters the dummy value at X[0]. Another minor improvement can be made by keeping the value of X[j] in a separate variable rather than as an array element. We expect that a compiler will produce code to access a variable more efficiently than an array element.
The average number of comparisons done by Insertion Sort on randomly ordered data is approximately n2/4. The number done in the worst case is n2/2. In the best case — which is when the data is already sorted — the number of comparisons done is approximately n.
The fact that the average number of combined with the fact that the inner loop of the Insertion Sort algorithm is simpler than Bubble Sort's inner loop, suggests that Insertion Sort should be at least twice as fast as Bubble Sort. In fact, the version of Insertion Sort in Listing 2 takes less as fast as Bubble Sort. In fact, the version of Insertion Sort in Listing 2 takes less than 40% of the time taken by the version of Bubble Sort in Listing 1.
The problem with both Bubble Sort and Insertion Sort, however, is that they both move data elements to their correct positions one place at a time. It can be shown that the average distance that a data element in a randomly ordered array containing n elements must travel to its correct position is n/3. If n is large, and if an element moves to its correct position one place at a time, this represents a large number of operations.
Quicksort was invented by C.A.R, Hoare in the early 1960s. The basic idea is very simple but relies on a concept called recursion: the ability of a procedure or subroutine to call itself. Hoare remarked on the importance of recursion in a lecture he gave the day he received the 1980 ACM Turing award, "I first learned about recursive procedures [around Easter 1961] and saw how to program the sorting method which I had earlier found such difficulty in explaining."
Quicksort sorts segments of an array. To sort an entire array, it sorts the segment from 1 through n. It works by taking a partitioning element from the array and rearranging the array so that all elements on the left-hand side preceed the partitioning element, all the elements on the right-hand side follow the partitioning element, and the partitioning element is placed between the left- and right-hand sides. It then recursively sorts the left- and right-hand segments.
Quicksort's advantage over Bubble Sort and Insertion Sort comes from the fact that the partitioning method exchanges non-adjacent elements, causing each element to migrate to its correct position in the array with many fewer operations.
The key problem is identifying a good partitioning element. Ideally, about half of the elements in the segment being sorted should preceed it and about half should follow it. A simple implementation of Quicksort is given in Listing 3 (printed here and also available as disk file SORT3.LTG on the buletin board service). This implementation is a pedagogical one and is not intended to be used in an application program. It consists of a recursive procedure, BQS, which does the actual sorting, followed by a procedure, BasicQuickSort, which sets things up and calls BQS. The implementation in Listing 3 simply uses the first elements of the segment as a partitioning element. Assuming the array elements are in random order, this is not a bad choice. However, if the array is not in random order (e.g., it already happens to be sorted), this choice can be disastrous.
Once the partitioning element is identified, the segment is scanned from the left until the first element not preceeding the partitioning element is encountered. The segment is then scanned from the right, stopping at the last element not following the partitioning element. When these two elements are located, they are exchanged. The two scanning processes continue until they meet in the middle of the segment. Partitioning is completed when the partitioning element is inserted at the meeting point.
This version of Quicksort can be shown to take about 2n log2n comparisons on randomly ordered data. The fact that the function log 2n is much smaller than n for large values of n (e.g., log21000 is about 10) implies that, for large n, Quicksort will do many fewer comparisons on the average than Bubble Sort or Insertion Sort. In the worst case, Quicksort does about n2/2 comparisons, which is as bad as Bubble Sort.
What is worrisome about this version of Quicksort, however, is that the algorithm is at its worst processing already sorted data. When the array is in order, choosing the first element of a segment of a size s as a partition element gives two sub-segmenis of a size 0 and size s-1. Quicksort operates most efficiently when partitioning results in two sub-segments of nearly equal size. The version of Quicksort in Listing 3 — which is the most easily understood version — should not be used unless you are certain that the array to be sorted is in random order.
An enhanced version of Quicksort is given in Listing 4 (available only on the bulletin board service as file SORT4.LTG). Again, I present a recursive routine, QS, followed by a routine, Quicksort, which calls QS and then does some final computations. Table 1 shows that these improvements give small decreases in run time over the version presented in Listing 3. The enhanced version's most important advantage — which does not appear in the table — is that it is less likely to behave badly on non-random data.
The most important feature of a Quicksort implementation is the selection of the partitioning element. Rather than simply taking the first element of the segment — on the assumption that it is randomly located within the partition — take the median element of the first, middle, and last elements of the segment. If the array is already ordered (or nearly ordered), this is obviously a good choice. For a randomly ordered array, it is also a good choice and gives a partitioning element that is closer to the middle point than the first element. (The average number of comparisons goes down from 2n log2n to (12/7)n log2n.) Some people like to partition the segment using the numerical average of the first and last elements, but this won't work very easily if you are sorting non-numeric data.
Another improvement can be made by noting the fact that the procedure BQS ends with a recursive call. This call can be removed by setting the values of the parameters appropriately and re-executing the body of the procedure. This is often described as tail recursion. It is also desirable to limit the depth of recursive calls because deep recursive calls use more memory and a recursive call is often more time consuming than re-executing the procedure block. In the procedure QS, this is achieved by doing the recursive call on the shorter segment and using tail recursion on the longer segment. Doing this guarantees the depth of recursion will never exceed log2n.
The final improvement comes from the fact that for very small segments, Insertion Sort is more efficient than Quicksort because of Quicksort's complexity. This means that when the array is almost sorted, it is better to abandon Quicksort and finish the job with Insertion Sort. By doing this you can sort data elements most efficiently since every element is near its final position. This is done in the procedure QS; QS does not sort a segment unless its length is greater than M — a conslant in the procedure. The value of M depends on the specific implementation. In Donald E. Knuth's The Art of Computer Programming, vol 3, Sorting and Searching (pp. 119-122), you can see how the best value of Mcan be found in a sample assembly language implementation. Knuth uses information on instruction timing and some subtle mathematical analysis of the probability of taking different paths in the procedure. 
procedure BubbleSort (var X : DataArray; n : integer);
var
    j,
    Limit,  {data at position above here is in final position}
    LastSwap{holds position of last data pair swapped }
        : integer;
begin 
    Limit := n;
    while not (Limit = 0) do
        begin
            LastSwap := 0;
            for j := 1 to Limit-1 do
                if X[j] > X[j+1] then
                    begin
                        swap(X[j], X[j+1]);
                        LastSwap := j
                    end;
            Limit := LastSwap
        end
end;
Listing 1. 
procedure InsertionSort (var X : DataArray; n : integer);
var
    j, i : integer;
    Z {temporarily holds X[j] while X[j-1],..are being moved up}
      : real;
begin 
    X[0] := SmallerThanAnything;
    for j := 2 to n do
        begin 
            Z := X[j];
            i := j - 1;
            while (Z < X[i]) do
                begin
                    X[i+1] := X[i];
                    i := i - 1
                end;
            X[i+1] := Z
        end
end;
Listing 2.
A simpler approach is to find the value of M by experimentation. For example, with my machine and my compiler running this procedure, the correct value of M was 12. However, the value of M is not critical. The execution times for this version of M, sorting an array of 5,000 elements, with QS =6 and M =18, were only about 2% greater than with M equal to 12. M equals 10 is usually a safe choice.
So, which sorting algorithm is the best to use? If the array to be sorted is small (e.g., substantially less than 100 elements), or if the data lobe sorted is already nearly ordered, then Insertion Sort is a reasonable choice. Otherwise, use an enhanced version of Quicksort like the one given in Listing 4. Conventional wis dom says this is the fastest "average case" sorting algorithm and the choice of the median element as the partitioning element gives good protection against cases where the data to be sorted is in extremely random order.
Mathematical proofs of many of the assertions made in this article can be found in Donald Knuth's book The Art of Computer Programming, vol 3, Sorting and Searching, published by Addison-Wesley, 1975. Anyone who is interested in the more subtle problems connected with sorting algorithms will find an incredible wealth of information in that volume.
The algorithms presented in Listing 1, 2, 3, and 4 were compiled using Microsoft Pascal (version 3.13) and run 10 times each on various sizes of arrays filled with random real numbers on an IBM XT with an 8087 chip under DOS 2.0. The results are presented in Table 1. Since the resolution of the system clock under DOS is only 0.05 sec, the timing for the two versions of Quicksort for the smallest values of n should not be taken very seriously.

Richard Larson received a B.S. from the University of Pennsylvania, an M.S. and Ph.D. from the University of Chicago — all in the field of mathematics. He then went on to teach at M.I.T. and the University of Illinois at Chicago. While on sabbatical leave at Rutgers University in 1974, he became interested in applying computers to abstract mathematics. He is currently a professor in the Dept. of Mathematics, Statistics, and Computer Science at the University of Illinois at Chicago. 
                                      Simple     Enhanced 
     n      Bubble    Insertion        Quick        Quick 

   125        1.64         0.63         0.16         0.16 
   250        6.38         2.35         0.37         0.35 
   500       25.48         9.24         0.81         0.76 
  1000      102.40        36.50         1.80         1.69 
  2000      411.57       145.99         4.02         3.67
Table 1. 
procedure BQS (var X : DataArray; i, j : integer);
{ procedure called by BasicQuickSort to do actual sorting }
var
    left, right : integer;
    Z : real;
begin
{Partition the array segment X[i]..X[j] using X[i] as partitioning element}
    Z := X[i];
    left := i;
    right := j + 1;
    while (left < right) do
        begin
            repeat
                left := left + 1
            until X[left] >= Z;
            repeat
                right := right - 1
            until X[right] <= Z;
            if left < right then
               swap(X[left], X[right])
        end;
     X[i] := X[right];
     X[right] := Z;
{At this point we have: for all k < right, X[k] <= X[right];
                        for all k > right, X[k] >= X[right].
 Recursively sort the segments X[i]..X[right-1] and X[right+1]..X[j].}
    if i < right-1 then
        BQS(X, i, right-1);
    if right+1 < j then
        BQS(X, right+1, j)
end;

procedure BasicQuickSort (var X ; DataArray; n : integer);
begin
    X[n+1] := LargerThanAnything;
    BQS(X, 1, n)
end;
Listing 3.

HTML-Bearbeitung von Werner Cirsovius
Januar 2015
© CL Publications