Quicksort algorithm in ada

Quicksort algorithm in ada

[Thomas Krueger]

Hi

Does the quicksort algorithm already exists in the Ada standardlibrary? I 
didn't find it. The only similar thing i found was bubblesort in the gnat 
library...

Do you know the trick or a link to a good Ada implementation of quicksort.

Thanks
Thomas 

Re: Quicksort algorithm in ada

[Lutz Donnerhacke]

* Thomas Krueger wrote:
> Do you know the trick or a link to a good Ada implementation of quicksort.

The classic algorithm is easy to implement. You are free to make it generic.

with Ada.Text_IO;
use  Ada.Text_IO;

procedure t is
  procedure qsort(f : in out String) is
    procedure swap(i,j : Positive) is
      t : Character := f(i);
    begin
      f(i) := f(j);
      f(j) := t;
    end swap;

    i : Natural := f'First;
    j : Natural := f'Last;
  begin
    if f'Length > 1 then
      while i<j loop
        while i<j loop
	  if f(i) > f(j) then
	    swap(i,j);
	    j := Positive'Pred(j);
	    exit;
	  end if;
	  i := Positive'Succ(i);
        end loop;
        while i<j loop
	  if f(i) > f(j) then
	    swap(i,j);
	    i := Positive'Succ(i);
	    exit;
	  end if;
	  j := Positive'Pred(j);
  	end loop;
      end loop;
      qsort(f(f'First .. Positive'Pred(j)));
      qsort(f(Positive'Succ(i) .. f'Last));
    end if;
  end qsort;
  
  buff : String(1 .. 80);
  last : Natural;
begin
  Get_Line(buff, last);
  qsort(buff(buff'First .. last));
  Put_Line(buff(buff'First .. last));
end t;

Re: Quicksort algorithm in ada

[Gautier]

Thomas Krueger:

> Does the quicksort algorithm already exists in the Ada standardlibrary? I 
> didn't find it. The only similar thing i found was bubblesort in the gnat 
> library...
> 
> Do you know the trick or a link to a good Ada implementation of quicksort.

You'll find one there (non-recursive), among other algorithms:

   http://www.mysunrise.ch/users/gdm/e3d_html/eng3dsor__adb.htm

The key array sorted there is "Center_Z" and another
array "Order" is sorted at the same time.
Should be easy to make it generic or specific to any application.
HTH
_______________________________________________________________
Gautier         -- http://www.mysunrise.ch/users/gdm/index.htm
Ada programming -- http://www.mysunrise.ch/users/gdm/gsoft.htm

NB: For a direct answer, e-mail address on the Web site!

Re: Quicksort algorithm in ada

[Robert A Duff]

"Thomas Krueger" <thomas.krueger2@uni-rostock.de> writes:

> Does the quicksort algorithm already exists in the Ada standardlibrary? I 
> didn't find it. The only similar thing i found was bubblesort in the gnat 
> library...

The GNAT library also has heap sort.

- Bob

Re: Quicksort algorithm in ada

[Georg Bauhaus]

Thomas Krueger wrote:
> Hi
> 
> Does the quicksort algorithm already exists in the Ada standardlibrary? I 
> didn't find it. The only similar thing i found was bubblesort in the gnat 
> library...

The next Ada stadard library is going to have
Ada.Containers.Generic_Anonymous_Array_Sort,
which might be what you want.

If you have a recent GNAT, it's already there.

IIRC, the Booch components contain quicksort, too.

Re: Quicksort algorithm in ada

[Georg Bauhaus]

Georg Bauhaus wrote:

> The next Ada stadard library is going to have
> Ada.Containers.Generic_Anonymous_Array_Sort,

Ada.Containers.Generic_Array_Sort
Ada.Containers.Generic_Constrained_Array_Sort

sorry.

Re: Quicksort algorithm in ada

[Thomas Krueger]

Hi,

thank you for the advice. I prefer the solution in the Ada library.

ada.Containers.Generic_Array_Sort

Thomas 

Re: Quicksort algorithm in ada

[Matthew Heaney]

The original GNAT implementation of Generic_Array_Sort used a
quicksort, but that generic algorithm was recently changed (it was a
few weeks ago) to use a more efficient (and predictable) heap sort.

Check your implementation (I think the gnat runtime files are in
adainclude) to see whether you have the old quicksort or the new
heapsort implementation.

-Matt

Re: Quicksort algorithm in ada

[Jeffrey R. Carter]

Thomas Krueger wrote:
> 
> Does the quicksort algorithm already exists in the Ada standardlibrary? I 
> didn't find it. The only similar thing i found was bubblesort in the gnat 
> library...

The PragmAda Reusable Components include an implementation of quick sort. It 
uses insertion sort for short arrays and excludes the pivot from recursion. The 
library also includes implementations of insertion and heap sorts.

http://pragmada.home.mchsi.com/

-- 
Jeff Carter
"You couldn't catch clap in a brothel, silly English K...niggets."
Monty Python & the Holy Grail
19