pragma title("Tri de SHELL");
	--*******************************************
	--*    TRI PAR LA METHODE DE   S H E L L    *
	--*******************************************

generic
  type ELEMENT is private;		-- type des elements a trier.
  type VECTEUR_D_ELEMENTS is array (NATURAL range <>) of ELEMENT;
  with function "<" (elt1,elt2: ELEMENT) return BOOLEAN is <>;

procedure TRI_SHELL (VECTEUR: in out VECTEUR_D_ELEMENTS);
pragma title("Tri de SHELL");
	--*******************************************
	--*    TRI PAR LA METHODE DE   S H E L L    *
	--*******************************************

procedure TRI_SHELL (VECTEUR: in out VECTEUR_D_ELEMENTS) is

  incr: natural:=VECTEUR'length;   -- suite des increments degressifs.

  inf: constant natural:=VECTEUR'first;
  L_element: ELEMENT;
  K:integer;

begin   	-- corps du tri.

  while incr > 1 loop
	if incr < 5 then incr:=1;
		    else incr:= (5*incr-1) / 11;
	end if;

    -- Invariant de la boucle L:
    --   Les INCR sous_files imbriquees de VECTEUR (inf:L-1)
    --   sont ordonnees.

	for L in inf+incr .. VECTEUR'last loop
	    L_element:= VECTEUR (L);		-- sauvegarde.

		-- Recherche sequentielle retrograde de la place
		-- de L_ELEMENT, et decalage en parallele.

	    K:=L-incr;
	    while K >= inf loop
	    	if L_element < Vecteur (k) then
	       	   VECTEUR (k+incr):= VECTEUR (k);
		   k:=k-incr;
	    	else
	           exit;			-- fin du decalage.
		end if;
	    end loop;	-- k.
	    VECTEUR (k+incr):=L_element;	-- insertion.
	end loop;	-- l.
  end loop;		-- incr.

end  TRI_SHELL;