From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00,
	REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4
X-Google-Thread: 103376,587e0e0a16d65b10
X-Google-Attributes: gid103376,domainid0,public,usenet
X-Google-Language: ENGLISH,ASCII-7-bit
Path: 
 g2news2.google.com!news3.google.com!feeder1-2.proxad.net!proxad.net!feeder2-2.proxad.net!newsfeed.arcor.de!newsspool4.arcor-online.net!news.arcor.de.POSTED!not-for-mail
From: "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>
Subject: Re: Invade wikipedia!
Newsgroups: comp.lang.ada
User-Agent: 40tude_Dialog/2.0.15.1
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Reply-To: mailbox@dmitry-kazakov.de
Organization: cbb software GmbH
References: <l6k0og.o0o.ln@hunter.axlog.fr>
 <go4gqp$5nj$1@octagram.motzarella.org> 	<gir5og.o5s.ln@hunter.axlog.fr>
 <go66s6$m76$1@octagram.motzarella.org>
 	<49a6d506$0$32680$9b4e6d93@newsspool2.arcor-online.net>
 <4a18f335-30f6-4216-8376-0310eb560445@p11g2000yqe.googlegroups.com>
 <49a7ced2$0$31342$9b4e6d93@newsspool4.arcor-online.net>
 <t0tq29ariugm.aftb8vcp4aeg$.dlg@40tude.net>
 <49ae7bbf$1_1@glkas0286.greenlnk.net>
Date: Wed, 4 Mar 2009 14:46:20 +0100
Message-ID: <srtflu8nsew.hkpkh8pk8o2f.dlg@40tude.net>
NNTP-Posting-Date: 04 Mar 2009 14:46:20 CET
NNTP-Posting-Host: 4bb05923.newsspool1.arcor-online.net
X-Trace: 
 DXC=DeR7_18:?L=T2Rfi6<W9f5ic==]BZ:af>4Fo<]lROoR1^YC2XCjHcb9?@AV>hR\\>:DNcfSJ;bb[5FCTGGVUmh?4LK[5LiR>kg2DC]IU772jA5
X-Complaints-To: usenet-abuse@arcor.de
Xref: g2news2.google.com comp.lang.ada:4901
Date: 2009-03-04T14:46:20+01:00
List-Id: <comp.lang.ada>

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