Pascal language - Recursion within a Shell Sort

December 2016




Definition


Recursion, in the computing or mathematical terms, is a method of defining functions in which the function being defined is applied within its own designation. The term is also used more generally to describe the process of repeating objects in a similar pattern.

Implementation


Here below you will find a simple recursive procedure allowing you to sort a table of (n) number of integers using the Shell sorting method:

Procedure Shell_Sort_Rec (Var t: TAB; n,h : integer); 
Var aux,i : integer; 
begin 
    If h > 0 Then 
    Begin 
        If n > h Then 
             begin 
                  Shell_Sort_Rec (t,n - h,h); 
                  If t[n] < t[n - h] Then 
                  Begin 
                     aux:= t[n]; 
                     i := n; 
                     Repeat                         
                        t[i] := t[i - h]; 
                        i := i - h; 
                     Until (i = h) Or (aux > t[i - h]); 
                     t[i] := aux; 
                  End; 
              End; 
        Shell_Sort_Rec (t,n,h Div 3); 
    End; 
End;

Notes


It is better to test this procedure on small tables, because in the case that the number of calls becomes too important may spillover the limits of the memory stack allocate to recursive function. You can increase the size of the test table on increasing the size of the stack:

OptioncompilerMemory Settingsstack size 

Related :

This document entitled « Pascal language - Recursion within a Shell Sort » from CCM (ccm.net) is made available under the Creative Commons license. You can copy, modify copies of this page, under the conditions stipulated by the license, as this note appears clearly.