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=-1.9 required=5.0 tests=BAYES_00
	autolearn=unavailable autolearn_force=no version=3.4.4
Path: 
 eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail
From: Simon Wright <simon@pushface.org>
Newsgroups: comp.lang.ada
Subject: Re: Quick Sort in Rosetta Code
Date: Wed, 10 Feb 2016 20:41:23 +0000
Organization: A noiseless patient Spider
Message-ID: <lylh6s5mdo.fsf@pushface.org>
References: <2e3f8f3d-9247-4294-9ee7-961547674bc3@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: mx02.eternal-september.org;
 posting-host="76d0af23e4f91faeb8b7e716c028eccc";
	logging-data="15302"; mail-complaints-to="abuse@eternal-september.org";
	posting-account="U2FsdGVkX1/etmfgKTpCKlmUVZL8FRazii/lOOlij6I="
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (darwin)
Cancel-Lock: sha1:Dt0hPNFsw8XeAGNsBQ/dtL4bOa0=
	sha1:Tryrpccr1JysKhr0Ui9ZWEKK4sQ=
Xref: news.eternal-september.org comp.lang.ada:29482
Date: 2016-02-10T20:41:23+00:00
List-Id: <comp.lang.ada>

gautier_niouzes@hotmail.com writes:

> Couldn't not find how to reach the author of the Rosetta Code Quick Sort code
>   http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Ada
> ...but the code needs some improvement.
>
> If you put 
>       Wed => 99.0, 
> in the demo instead of
>       Wed => 800.0, 
> you get
>    99.00  100.00  300.00  200.00  500.00  700.00  900.00

Yes.

I thought this might be an interesting introduction to gnatprove (GPL
2015), and was disappointed to find that it doesn't support quantified
expressions! so you have fun writing them out longhand, which means in
the body.

I have no idea why the C code at rosettacode.org works and the Ada
doesn't, and it's not helped by having no idea what the partitioning
loop is trying to do! which makes it hard to write assertions.

   void quick_sort (int *a, int n) {
       int i, j, p, t;
       if (n < 2)
           return;
       p = a[n / 2];
       for (i = 0, j = n - 1;; i++, j--) {
           while (a[i] < p)
               i++;
           while (p < a[j])
               j--;
           if (i >= j)
               break;
           t = a[i];
           a[i] = a[j];
           a[j] = t;
       }
       quick_sort(a, i);
       quick_sort(a + i, n - i);
   }