How to resolve the algorithm Sorting algorithms/Shell sort step by step in the Ada programming language

Published on 12 May 2024 09:40 PM
#Ada

How to resolve the algorithm Sorting algorithms/Shell sort step by step in the Ada programming language

Table of Contents

Problem Statement

Sort an array of elements using the Shell sort algorithm, a diminishing increment sort. The Shell sort   (also known as Shellsort or Shell's method)   is named after its inventor, Donald Shell, who published the algorithm in 1959. Shell sort is a sequence of interleaved insertion sorts based on an increment sequence. The increment size is reduced after each pass until the increment size is 1. With an increment size of 1, the sort is a basic insertion sort, but by this time the data is guaranteed to be almost sorted, which is insertion sort's "best case". Any sequence will sort the data as long as it ends in 1, but some work better than others. Empirical studies have shown a geometric increment sequence with a ratio of about 2.2 work well in practice. [1] Other good sequences are found at the On-Line Encyclopedia of Integer Sequences.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sorting algorithms/Shell sort step by step in the Ada programming language

Source code in the ada programming language

generic
   type Element_Type is digits <>;
   type Index_Type is (<>);
   type Array_Type is array(Index_Type range <>) of Element_Type;
package Shell_Sort is
   procedure Sort(Item : in out Array_Type);
end Shell_Sort;


package body Shell_Sort is
   
   ----------
   -- Sort --
   ----------

   procedure Sort (Item : in out Array_Type) is
      Increment : Natural := Index_Type'Pos(Item'Last) / 2;
      J : Index_Type;
      Temp : Element_Type;
   begin
      while Increment > 0 loop
         for I in Index_Type'Val(Increment) .. Item'Last loop
            J := I;
            Temp := Item(I);
            while J > Index_Type'val(Increment) and then Item (Index_Type'Val(Index_Type'Pos(J) - Increment)) > Temp loop
               Item(J) := Item (Index_Type'Val(Index_Type'Pos(J) - Increment));
               J := Index_Type'Val(Index_Type'Pos(J) - Increment);
            end loop;
            Item(J) := Temp;
         end loop;
         if Increment = 2 then
            Increment := 1;
         else
            Increment := Increment * 5 / 11;
         end if;
      end loop;
   end Sort;

end Shell_Sort;

You may also check:How to resolve the algorithm Draw a cuboid step by step in the Tcl programming language
You may also check:How to resolve the algorithm Self-describing numbers step by step in the UNIX Shell programming language
You may also check:How to resolve the algorithm Munchausen numbers step by step in the Dc programming language
You may also check:How to resolve the algorithm Padovan n-step number sequences step by step in the Raku programming language
You may also check:How to resolve the algorithm Caesar cipher step by step in the Eiffel programming language