Re: Invade wikipedia!

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Wed, 4 Mar 2009 13:20:54 -0000, Stuart wrote:

> 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 think this is because the inner loop became a for-loop. I wonder if it
wouldn't be even more efficient (for integral element types) not to move
any elements while looking after the insertion point. And then move slices
when the insertion point is found:

   A (Insertion_Point + 1..I) := A (Insertion_Point..I - 1);
   A (Insertion_Point) := Next_Value_to_Insert;

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de