Quick Sort in Rosetta Code

Quick Sort in Rosetta Code

[gautier_niouzes]

Hello,

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

o-O !

Additionally a generic profile compatible with Ada 2005's 
  Ada.Containers.Generic_Array_Sort
and a remark about its existence would be good...

Cheers
_________________________ 
Gautier's Ada programming 
http://sf.net/users/gdemont/

Re: Quick Sort in Rosetta Code

[Jeffrey R. Carter]

On 02/09/2016 10:27 PM, gautier_niouzes@hotmail.com wrote:
> 
> 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

Not quite right. There's an implementation of Quick Sort in the PragmARCs, but
it would use insertion sort for something this short.

-- 
Jeff Carter
"I was in love with a beautiful blonde once, dear.
She drove me to drink. That's the one thing I'm
indebted to her for."
Never Give a Sucker an Even Break
109

Re: Quick Sort in Rosetta Code

[Leo Brewin]

I bumped inthis problem ages ago. I think the error is that the pair of if statements in the Rosetta code

         if Left < Item'Last then
            Left := Index_Type'Succ(Left);
         end if;
         if Right > Item'First then
            Right := Index_Type'Pred(Right);
         end if;

should be merged as a single if statement

         if Left < Item'Last and Right > Item'First then
            Left := Index_Type'Succ(Left);
            Right := Index_Type'Pred(Right);
         end if;

This seems to fix the problem.

Cheers,
Leo

Re: Quick Sort in Rosetta Code

[Leo Brewin]

I missed one other change, in the second last if statement the Rosetta code was

   Sort(Item(Item'First..Index_Type'Pred(Right)));

I think that should be

   Sort(Item(Item'First..Index_Type'Pred(Left)));

Here is the complete code

procedure Sort (Item : in out Element_Array) is

   procedure Swap(Left, Right : in out Element_Type) is
      Temp : Element_Type := Left;
   begin
      Left := Right;
      Right := Temp;
   end Swap;

   Pivot_Index : Index_Type;
   Pivot_Value : Element_Type;
   Right       : Index_Type := Item'Last;
   Left        : Index_Type := Item'First;

begin
   if Item'Length > 1 then
      Pivot_Index := Index_Type'Val((Index_Type'Pos(Item'Last) + 1 +
                                     Index_Type'Pos(Item'First)) / 2);
      Pivot_Value := Item(Pivot_Index);

      Left  := Item'First;
      Right := Item'Last;
      loop
         while Left < Item'Last and then Item(Left) < Pivot_Value loop
            Left := Index_Type'Succ(Left);
         end loop;
         while Right > Item'First and then Item(Right) > Pivot_Value loop
            Right := Index_Type'Pred(Right);
         end loop;
         exit when Left >= Right;
         Swap(Item(Left), Item(Right));
         if Left < Item'Last and Right > Item'First then
            Left := Index_Type'Succ(Left);
            Right := Index_Type'Pred(Right);
         end if;
      end loop;
      if Right > Item'First then
         Sort(Item(Item'First..Index_Type'Pred(Left)));
      end if;
      if Left < Item'Last then
         Sort(Item(Left..Item'Last));
      end if;
   end if;
end Sort;

Re: Quick Sort in Rosetta Code

[gautier_niouzes]

On Wednesday, February 10, 2016 at 8:14:52 AM UTC+1, Leo Brewin wrote:
>       if Right > Item'First then
>          Sort(Item(Item'First..Index_Type'Pred(Left)));
>       end if;

Mmmh... make no sense either: why a test with Right to prevent an out-of-range on Index_Type'Pred(Left) ?...

Re: Quick Sort in Rosetta Code

[gautier_niouzes]

I did not dig too far into the fixing (the tricky thing is to avoid going out of range with indices) but here is, as an inspiration, a simplified case where the index type is integer, and this one is working (I've taken the C version to start with):

with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random;

--with Ada.Text_IO; use Ada.Text_IO;

procedure Qsort is

  type Item_array is array(Integer Range <>) of Float;

  procedure Quick_sort (a: in out Item_array) is
    n: Integer:= a'Length;
    i, j: Integer;
    p, t: Float;
  begin
    if n < 2 then
      return;
    end if;
    p := a(n / 2 + a'First);
    i:= 0;
    j:= n - 1;
    loop
      while a(i + a'First) < p loop
        i:= i + 1;
      end loop;
      while p < a(j + a'First) loop
        j:= j - 1;
      end loop;
      exit when i >= j;
      t := a(i + a'First);
      a(i + a'First) := a(j + a'First);
      a(j + a'First) := t;
      i:= i + 1;
      j:= j - 1;
    end loop;
    Quick_sort(a(a'First .. a'First + i - 1));
    Quick_sort(a(a'First + i .. a'Last));
  end;

  gen: Generator;

begin
  Reset(gen);
  for n in 1..100 loop
    for round in 1..500 loop
      declare
        start: Integer:= Integer(10.0 * (Random(gen)-0.5));
        a: Item_array(start .. start + n - 1);
      begin
        for i in a'Range loop
          a(i):= Random(gen);
        end loop;
        Quick_sort(a);
        for i in a'Range loop
          -- Put_Line(Float'Image(a(i)));
          if i > a'First and then a(i-1) > a(i) then
            raise Program_Error;  --  Buggy sorting
          end if;
        end loop;
      end;
    end loop;
  end loop;
end;
_________________________ 
Gautier's Ada programming 
http://sf.net/users/gdemont/ 

Re: Quick Sort in Rosetta Code

[robin.vowels]

On Wednesday, February 10, 2016 at 4:43:11 PM UTC+11, Jeffrey R. Carter wrote:
> On 02/09/2016 10:27 PM, g.nospam@hotmail.com wrote:
> > 
> > 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
> 
> Not quite right. There's an implementation of Quick Sort in the PragmARCs, but
> it would use insertion sort for something this short.

The Rosetta Quicksort is about Quicksort,
not about Insertion Sort.

Re: Quick Sort in Rosetta Code

[Simon Wright]

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

Re: Quick Sort in Rosetta Code

[Jeffrey R. Carter]

On 02/10/2016 06:50 AM, robin.vowels@gmail.com wrote:
> On Wednesday, February 10, 2016 at 4:43:11 PM UTC+11, Jeffrey R. Carter wrote:
>>
>> Not quite right. There's an implementation of Quick Sort in the PragmARCs, but
>> it would use insertion sort for something this short.
> 
> The Rosetta Quicksort is about Quicksort,
> not about Insertion Sort.

Yes, of course. A simple O(N**2) sorting algorithm is faster than Quick Sort for
short arrays, so a sorting pkg for real-world use (such as the PragmARCs) should
use such an algorithm for short arrays rather than invoke the overhead of Quick
Sort.

However, the PragmARC Quick Sort is well tested; if someone wants to take out
the test for a short array and submit it to Rosetta Code, that would be fine.

-- 
Jeff Carter
"You tiny-brained wipers of other people's bottoms!"
Monty Python & the Holy Grail
18