Re: Quick Sort in Rosetta Code

[gautier_niouzes@hotmail.com]

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/