Re: Quicksort

["Johan Stäring" <f97johan@dd.chalmers.se>]

Hi Jamie!

You might be able to get the general idea through this code sample. It's
more or less written as one would a generic implementation, but I don't
think that will be a problem.

Oh, I wonder how many toes I've stepped on with my personal somewhat
inconsistent naming convention... ;-) 

	/Johan

---8<----

type Index is (integer range <>);
type Field_Type is array 1..n of Element_Type;
with procedure Swap (a, b : Index);
	--Function that swaps Field(a) & Field(b)
Field : Field_Type;

procedure Quicksort (Low, High : Index) is
  Pivot, Middle : Index;
begin
  Pivot := Findpivot (Low, High);
  if Pivot /= 0 then
    Middle := Partition (Low, High, Pivot);
    Quicksort (Low, Middle - 1);
    Quicksort (Middle, High);
  end if;
end Quicksort;

function Findpivot (Low, High : Index) return Index is
begin
  for i in Low+1..High loop
    if Field(Low) < Field(i) then
      return i;
    elseif Field(Low) > Field(i) then
      return Low;
    end if;
  end loop;
  return 0;
end Findpivot;

function Partition (Low, High, Pivot : Index) return Index is
  Left      : Index := Low;
  Right     : Index := High;
  Pivotelem : Element_Type := Field(Pivot);
begin
  loop
    while Left < Right and then Field(Left) < Pivotelem loop
      Left := Left + 1;
    end loop;
    while Left < Right and then Field(Right) >= Pivotelem loop
      Right := Right - 1;
    end loop;
  exit when Left >= Right;
    Swap (Left, Right);
  end loop;
  return Left;
end Partition;

---8<----

========================================================================
|| sob@cheerful.com ||  Johan St�ring  ||  Cell#: +46-(0)70-672 79 01 ||
||   sob@linux.nu   ||         Site of Repentance and Regrets         ||
||  ICQ#:  7290407  ||      http://www.dd.chalmers.se/~f97johan       ||
========================================================================