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=0.1 required=5.0 tests=BAYES_05,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII
X-Google-Thread: 103376,5052a1cdc3cdb4ab
X-Google-Attributes: gid103376,public
From: =?ISO-8859-1?Q?Johan_St=E4ring?= <f97johan@dd.chalmers.se>
Subject: Re: Quicksort
Date: 1998/07/29
Message-ID: <Pine.SOL.4.02.9807291617540.4362-100000@shagrat>#1/1
X-Deja-AN: 376001811
Content-Transfer-Encoding: 8BIT
References: <01bdbaef$d13c9340$86eba8c2@j.couston>
To: Jamie <j.couston@virgin.net>
X-Sender: f97johan@shagrat
Content-Type: TEXT/PLAIN; charset=ISO-8859-1
Organization: Chalmers University of Technology, Sweden
Mime-Version: 1.0
Newsgroups: comp.lang.ada
Date: 1998-07-29T00:00:00+00:00
List-Id: <comp.lang.ada>

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       ||
========================================================================