Re: Quicksort

[Hans-Malte Kern <kernhe@mickey.informatik.uni-stuttgart.de>]

On 29 Jul 1998, Jamie wrote:

On 29 Jul 1998, Jamie wrote:

> Hi,
>
> I was wondering if anyone could help me out with some source code. I wish
> to see a simple implementation of the Quicksort algorithm. As I'm still 
> a newcomer to Ada It would only have to deal with arrays of positive
> integers - but please can you make it a recursive NOT iterative process.

This one is taken from our informatic lecture

procedure Q_Sort(Field: in out Field_Type) is
 procedure Local_Q_Sort(L, R: in Index_Typ) is
  Left, Right: Integer range Field'First-1 .. Field'Last-1;
  Pivot: Element_Type;   
 begin
   Left:=L;
   Right:=R;
   Pivot:=Field((L+R)/2); --just take the midde
   while Left =< Right loop
     while Field(Left) < Pivot loop
       Left:=Left+1;
     end loop;
     while Field(Right) > Pivot loop
       Right:=Right-1;
     end loop;
     if Left =< Right then
       if Left < Right then
         swap(Field(Left), Field(Right));
       end if;
       Left:=Left + 1;
       Right:=Right-1;
     end if;
   end loop;
   if L<Right then local_q_sort(L, Right) end if;
   if R>Left  then Local_Q_Sort(Left, R)  end if;
 end Local_Q_Sort;
begin
 Local_Q_Sort(Field'First, Field'Last);
end Q_Sort;


farvel
  jimmy
--