[PASCAL] Shell Sort Algorithm

[CouldnoT]

Shell Sort Algorithm

 

This is a very fast sort when there is a large amount of data, and its behavior is similar to a bubble sort
if the data is semi-sorted, but it is more complicated than the two previous sort algorithms.

 

Its name comes from its inventor, Donald Shell.

 

How Shell Sort Works? ( source ) :
 

1. Suppose, we need to sort the following array.

   

   Initial array

2. We are using the shell's original sequence (N/2, N/4, ...1) as intervals in our algorithm.
   
   In the first loop, if the array size is N = 8 then, the elements lying at the interval of N/2 = 4 are compared and swapped if they are not in order.
   1. The 0th element is compared with the 4th element.
   2. If the 0th element is greater than the 4th one then, the 4th element is first stored in temp variable and the 0th element (ie. greater element) is stored in the 4th position and the element stored in temp is stored in the 0th position.

      

      Rearrange the elements at n/2 interval

      
      This process goes on for all the remaining elements.

      

      Rearrange all the elements at n/2 interval

3. In the second loop, an interval of N/4 = 8/4 = 2 is taken and again the elements lying at these intervals are sorted.

   

   Rearrange the elements at n/4 interval

   
   You might get confused at this point.

   

   All the elements in the array lying at the current interval are compared.

   
   The elements at 4th and 2nd position are compared. The elements at 2nd and 0th position are also compared. All the elements in the array lying at the current interval are compared.
4. The same process goes on for remaining elements.

   

   Rearrange all the elements at n/4 interval

5. Finally, when the interval is N/8 = 8/8 =1 then the array elements lying at the interval of 1 are sorted. The array is now completely sorted.

   

   Rearrange the elements at n/8 interval

    

    

   Script: 

    

   program ShellSort;
   uses
    cthreads,
    Classes;
   
   procedure ShellS(var X: array of Integer);
   var
    	Done: Boolean;
    	Jump, j, i: Integer;
    	Temp: Integer;
   begin
    	Jump:= High(X);
    	while (Jump > 0) do // Outer loop
    	begin
    		Jump:= Jump div 2;
   		repeat // Intermediate loop
   		Done:= True;
   		for j:= 0 to High(X) - Jump do // Inner loop
   		begin
   			 i:= j + Jump;
   			 if X[j] > X[i] then // Swap
   			 begin
    				Temp:= X[i];
    				X[i]:= X[j];
    				X[j]:= Temp;
    				Done:= False;
    			 end;
    		end; // end of inner loop
    		until Done; // end of intermediate loop
   	end; // end of outer loop
   end;
   
   var
    Numbers: array [0 .. 9] of Integer;
    i: Integer;
   
   begin
    	Writeln('Please input 10 random numbers');
    	for i:= 0 to High(Numbers) do
   	 begin
    		Write('#', i + 1, ': ');
   		 Readln(Numbers[i]);
   	 end;
   	 ShellS(Numbers);
   	 Writeln;
   	 Writeln('Numbers after Shell sort: ');
    	for i:= 0 to High(Numbers) do
    	begin
    		Writeln(Numbers[i]);
    	end;
    	Write('Press enter key to close');
    	Readln;
   end.

    

Edited August 25, 2020 by CouldnoT

[CouldnoT]

Edited October 21, 2020 by CouldnoT