Re: Quicksort

Re: Quicksort

[Hans-Malte Kern]

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

Re: Quicksort

[Johan Stäring]

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

Re: Quicksort

[Ellis E Hardin]

Jamie <j.couston@virgin.net> wrote:
> 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.

Try the Public Ada Library at
<http://wuarchive.wustl.edu/languages/ada/pal.html>.

Re: Quicksort

[Michael F Brenner]

Here is one student's method of programming quicksort downloaded from 
the Net.

  procedure quicksort (start, finish: heap_indices) is

    -- Quicksort the array LIST from left to right.

    highest: constant exacts := exacts (heap_indices'last);
    i:       exacts := exacts (start);
    j:       exacts := exacts (finish);
    left:    exacts := exacts (start);
    right:   exacts := exacts (finish);
    middle:  exacts;

    procedure swap (left, right: exacts) is
      temp: data;
    begin
      copy_datum (source=>get_random (warehouse, heap_indices (left)),
                  target=>temp);
      put_random (warehouse, heap_indices (left),
                  get_random (warehouse, heap_indices (right)));
      put_random (warehouse, heap_indices (right), temp);
    end swap;

  begin
    assert (heap_indices'first = 0);

    if left in 1..right-1 then
      middle := (left+right) / 2;
      assert (middle>0);
      assert (middle<=highest);
      declare
        X: keys;
      begin
        copy_key (get_key (middle), x);
        loop
          loop
            assert (i>0);
            assert (i<=highest);
            exit when get_key (i) >= X;
            i := i+1;
          end loop;
          loop
            -- if j=0 then
            --   os.low_level_display ("start=");
            --   os.low_level_display (heap_indices'image (start));
            --   os.low_level_display (" finish=");
            --   os.low_level_display (heap_indices'image (finish));
            --   os.low_level_display (" i=");
            --   os.low_level_display (exacts'image (i));
            --   os.low_level_display (" j=");
            --   os.low_level_display (exacts'image (j));
            --   os.low_level_display (" left=");
            --   os.low_level_display (exacts'image (left));
            --   os.low_level_display (" right=");
            --   os.low_level_display (exacts'image (right));
            --   os.low_level_display (" middle=");
            --   os.low_level_display (exacts'image (middle));
            -- end if;
            assert (j>0);
            assert (j<=highest);
            exit when X >= get_key (j);
            j := j-1;
          end loop;
          if i<=j then
            swap (i,j);
            i := i+1;
            j := j-1;
          end if;
          exit when i>j; -- Range left..i-1 is < X and j+1..right is > X.
        end loop;
        if left < j     then
          quicksort (start, heap_indices (j));
        end if;
        if i    < right then
          quicksort (heap_indices (i), finish);
        end if;
      end;
    end if;
  end quicksort;