Re: Invade wikipedia!

["Stuart" <stuart@0.0>]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:t0tq29ariugm.aftb8vcp4aeg$.dlg@40tude.net...
> On Fri, 27 Feb 2009 12:30:25 +0100, Georg Bauhaus wrote:
>
>> Adding the declarations of suitable number types in an example
>> algorithm maybe doesn't seem to hurt that much. Taking
>> http://en.wikipedia.org/wiki/Insertion_sort  as an example,
>> I tried
>>
>>    type Mug is (Metal, Plastic, Thermo, Porcelain);
>>    type Mug_Number is range 1 .. 10;
>>    type Mug_List is array(Mug_Number) of Mug;
<snip>

> You do not need T'Base in this case because it is cleaner and more
> efficient to rewrite it in a form that would always keep all indices 
> within
> the array range:
>
>   procedure Insertion_Sort (A: in out Mug_List) is
>   begin
>      for I in A'First + 1..A'Last loop
>         declare
>            Value : constant Mug := A (I);
>            J     : Mug_Number   := I - 1;
>         begin
>            while A (J) > Value loop
>               A (J + 1) := A (J);
>               exit when J = A'First;
>               J := J - 1;
>            end loop;
>            A (J) := Value;
>         end;
>      end loop;
>   end Insertion_Sort;
>
> Of course an Ada purist would also replace integer index arithmetic with
> I'Succ and I'Pred. But that would likely be too much for wiki brains...
> (:-))

I looked at the following:

package Sort is
   type Element is new integer; -- or whatever
   type Element_Number is range 1..10; -- or whatever
   type List is array(Element_Number) of Element;

   procedure Insertion_Sort(X : in out List);
end Sort;

package body Sort is
   procedure Insertion_Sort(X: in out List) is
   begin
      for I in X'First+1..X'Last loop
         declare
            Next_Value_to_Insert : constant Element := X(I);
            Insertion_Point : Element_Number := I;
         begin
            for J in reverse X'first .. I-1 loop
               exit when (Next_Value_to_Insert > X(J));
               X(J+1) := X(J); -- Shift greater values up the sorted list
               Insertion_Point := Insertion_Point - 1;
            end loop;
            A(Insertion_Point) := Next_Value_to_Insert;
         end;
      end loop;
   end Insertion_Sort;
end Sort;

Interestingly when the compiler I was using was set on a strong optimization 
mode it did a lot more loop unrolling in this case than for the other 
example.  I don't know whether this would have translated into any 
performance advantage.
-- 
  Stuart