Re: Quick Sort in Rosetta Code

[Simon Wright <simon@pushface.org>]

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);
   }