Sorting Algorithms in Pascal

Bubblesort

Note on Bubblesort

Bubblesort is a very basic algorithm that is very easy to understand. However, it is not very usefull in the real world, because there are algorithms that are faster on any type of input. The only advantage Bubblesort has, is that it not very susceptible to errors. This is important if stability and security rank higher in your program than speed.

Implementation of Bubblesort

The idea of Bubblesort is to go through the array for each element and compare it to its neighbor. If it is bigger than the neighbor, both are exchanged. If an element reaches goes all the way through to the end of the array, you can be sure that it is the biggest element. This also means that after you have done the comparision for the first i elements, the last i elements are in the correct position, because they have either be exchanged or "confirmed" in their places. A basic implementation looks like this:

procedure BubbleSort(var A: TArray); 
var 
  i, j: Integer; 
  Help: Byte; 
begin 
  for i := 1 to Size do { execute this loop for each element }
    for j := 1 to Size - i do { the last i elements are already in the correct position - see text }
      if A[j] > A[j + 1] then begin 
        Help := A[j]; A[j] := A[j + 1]; A[j + 1] := Help; { exchange } 
      end; 
end; 

This is the simplest way to sort an array - and a pretty slow one as well. If you take a closer look at what happens when the elements are moved through the array, you will find that a lot of times the array is already sorted some time before the algorithm is done. This means we could have skipped the rest of the compare and exchange operations. All you have to do is check whether you did any changes while comparing the current element with the array. If not the whole array is already in a sorted position. The next implementation takes this into account:

procedure BubbleSort(var A: TArray); 
var 
  i, j: Integer; 
  Help: Byte; 
  DidSwap: Boolean;  { flag to check for exchanges }
begin 
  for i := 1 to Size do begin  
    DidSwap := false;          { set the flag } 
    for j := 1 to Size - i do begin 
      if A[j] > A[Succ(j)] then begin 
        Help := A[j]; A[j] := A[Succ(j)]; A[Succ(j)] := Help;
        DidSwap := true;       { yes, we exchaged } 
      end; 
    end; 
    if not DidSwap then break;  { if there was no exchange -> done } 
  end; 
end; 

Please note that the last "optimization" only makes sense if an almost sorted array is likely to be the input! The setting of the flag also takes time.

Insertionsort

Implementation of Insertionsort

Insertionsort is similar to the method humans often use when sorting a deck of cards. You take each new element and insert it into the already sorted ones (at the correct position). Once you have done this, the array is sorted. Implemenation looks like this:

procedure Insertionsort(var A: TArray); 
var 
  i, j: Integer; 
  v: Byte; 
begin 
  A[0] := 0; { Boder to keep the algorithm from running out of the array } 
  for i := 2 to Size do begin { start at 2 since the first element is neither 
                                 smaller nor bigger than ifself } 
    v := A[i] ; j := i;  { copy the value into v, set the running marker to j} 
    while a[Pred(j)] > v do begin { if element before marker is bigger, keep moving } 
      A[j] := A[Pred(j)]; 
      dec(j); { we are running backwards }
    end; 
    A[j] := v;  { insert the value at the found position }  
  end; 
end; 

This implementation of Insertionsort uses a border-element to keep the algorithm from running out of the array (and causing a range overrun). It takes each element and moves backwards through the array from the position of the element to find the place where it has to be inserted. This saves the space for an additional array to store the sorted part of the array. While moving backwards through the array, each element is moved forward on space. The current element can therefore simply be inserted at the found position.

Shellsort

Implementation

Shellsort is an improved Insertionsort. Insertionsort is slow, because the elements are only move over one space at a time. You can now take bigger steps until you find the correct spot. If your step-width is 10, you cannot assume that an element is in the correct position if the (j - 10) th element is bigger than the current element. The current element could very well belong somewhere inbetween the j th and the (j - 10) th element.

An easy way to do this is to decrease the step-width k every time you found that the (j - k) th element is bigger than the than the current one. Dividing k by 3 every time. In Pascal code the whole thing looks like this:

procedure Shellsort(var A: TArray); 
var 
  k: Integer; 
  i, j: Integer; 
  v: Byte; 
label input; 
begin 
  k := 1; 
  repeat k := 3 * k + 1 until k > Size; { initialize k so it is big enough for the array } 
 
  repeat 
    k := k div 3; { divide k } 
    for i := Succ(k) to Size do begin 
      v := A[i]; 
      j := i; 
      while A[j - k] > v do begin 
        A[j] := A[j - k]; dec(j, k); 
        if j <= k then goto insert; 
      end; 
insert: 
    A[j] := v; 
    end; 
  until k = 1; 
end;

Quicksort

Note on Quicksort

Quicksort is probably the most popular sorting algorithm. On a random input with no specific qualities (that could be exploited for optimization) Quicksort is the fastest a the algorithms discussed here (I donīt say there is no faster one, but I donīt know any). Quicksort is a litte difficult to understand because it works recursively.

Implementation of Quicksort

Quicksort sorts the array the following way:

1. The value middle element v is taken. It is the element where the array is divided into two parts.
2. Then Quicksort runs through the array and puts every element bigger than v on the right side, every element that is smaller on the left. This way the array is presorted. It is made sure that very element left of v is smaller, every one right of it is bigger. Both parts are still unsorted.
3. Quicksort now calls itself and passes the two parts. When Quicksort is called with an array of size 1 it exits the recursion (an array with just one element is already sorted).
4. When Quicksort returns from recursion, the two parts have been sorted and can simply be put together into one big sorted piece (because they were presorted before the recursion).

Here is an implementation:

procedure Quicksort(var A: TArray; l, r: Integer); 
var 
  i, j: Integer; 
  Help, v: Byte; 
begin 
  v := A[(l + r) div 2]; { Wert des Teilungselements } 
 
  i := l; j := r; 
  repeat 
    while A[i] < v do inc(i); 
    while v < A[j] do dec(j); 
    if i <= j then begin 
      Help := A[i]; A[i] := A[j]; A[j] := Help; 
      inc(i); dec(j); { sonst kreuzen die sich nie } 
    end; 
  until i > j; { bis die Zeiger sich kreuzen } 
  if l < j then Quicksort(A, l, j); 
  if i < r then Quicksort(A, i, r); 
end; 

Letīs have a closer look at the presorting. What Quicksort actually does is this (this is the part inside the repeat ... until loop):

It starts form the left and runs throught the array, until it finds a element that is bigger than v (and should therefore be on the right side). Quicksort remembers the position of this element (variable i in this implementation). Then it does the same thing from the right. It now remembers the position of an element that should be on the left side. Then the elements are exchanged. This is the general case. However, there is also input like this:

 4 9 2 5 8 6 7

Here 5 would be v. The 9 from the left side should be on the right side. However, there is no element on the right side it could be exchanged with because those elements are all on the correct side. The 9 is exchanged with the 5. v is still 5 even though the value of the middle element is now longer 5. If this happens more than once, the element, where all elements on the left are smaller and all those on the right are bigger, is no longer the middle one. That is why the next level of the recursion is not call with:

{ this is wrong }
  if l < j then Quicksort(A, l, (i+j) div 2); 
  if i < r then Quicksort(A, (i+j) div 2 + 1, r); 

but like this:

{ this is right }
  if l < j then Quicksort(A, l, j); 
  if i < r then Quicksort(A, i, r);