Using Shell Sort to sort an Array in Delphi

     Shell sorting is a simple sorting algorithm and the implementation looks like this:

    {find the most efficient value for h}
    h := 1;
    repeat
         h := (3 * h) + 1;
    until (h > n);
    {shell sort}
    repeat
         h := h div 3;
         for i := h + 1 to n do begin
             value := AnArray[i];
             j := i;
             while (AnArray[j ­ h] > value) do begin
                  AnArray[j] := AnArray[j ­ h];
                  j := j ­ h;
                  if j <= h then goto Jumpout;
             end;
             Jumpout : AnArray[j] := Value;
         end;
    until (h = 1);

     In the included unit the shell sort outputs to a memo each completed step of the sort. With a small 10 element array the first line shows the array before sorting, and the following two lines follow the code through two iterations of the repeat loop.

21 75 78 59 29 12 3 17 73 43
21 12 3 17 29 43 78 59 73 75
3 12 17 21 29 43 59 73 75 78

     Through experience it has been demonstrated that the efficiency of a shell sort is determined by the values assigned to the variable 'h' and the algorithm above for calculating 'h' has been generally accepted as one of the most efficient. What is going to happen in ShellSort is that using a value further along in the array the code is going to 'look back' and if it finds that an element earlier in the array is greater than the current value further along then it is going to swap the positions of the two array elements. To keep an element from being lost during the swap it will be saved in the variable 'Value'.

      Using this simple example we can step through the code and determine what happens each step of the way, resulting in a sorted list in just a couple of iterations. When the array size is 10 the ideal value for h calculated from the formula shown above is '4'. H will then determine how many times the repeat loop is executed.

     The first loop through the for loop becomes i := 5 to 10. The value 29 in the 5th position is stored in the variable value. J is set equal to 5, the first value of i. Then the code looks back to see if the value in [j - h] is greater than the value stored in Value. In this case it is not, for 21 is less than 29. So the while loop never executes, and 29 remains where it was. The for loop continues, and the value in position 6 is stored in value (which would be 12 in the example above). Then the code looks back to position number 2 (j-h which is 6 - 4). In this case 75 is greater than 12 so now 75 is swapped into the place where 12 is, moving it further up the array. Then j becomes 2 {j-h which is 6 -2) and in this case j < h so the while loop executes and the value of 12 which was stored in value is put in spot 2, which was just vacated by the 75 (which over wrote the 12 which was in spot 6, indicating why the variable value is needed).

     This pattern is repeated until the array is sorted and if you want to view a visual output of the shell sorting routine, you can download the unit and see the sort step by step as it is output onto a memo on a form. The size of the array can be changed to any amount in the variable declaration section, for, as you will notice in the implementation, the code automatically adjusts (using the sizeof function) to any sized array. To change the size of the array simply change the variable declaration for the array.

     You can download the source code as a small unit here ... unit_shell_sort_array.txt ... Slap a button and a memo on a form, double click the button to intialize the event handler and then set the scrollbars on the memo before running the code.