* Re: Quicksort algorithm in ada
2006-04-12 13:43 Quicksort algorithm in ada Thomas Krueger
@ 2006-04-12 14:22 ` Lutz Donnerhacke
2006-04-12 15:04 ` Gautier
` (3 subsequent siblings)
4 siblings, 0 replies; 9+ messages in thread
From: Lutz Donnerhacke @ 2006-04-12 14:22 UTC (permalink / raw)
* 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;
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Quicksort algorithm in ada
2006-04-12 13:43 Quicksort algorithm in ada Thomas Krueger
2006-04-12 14:22 ` Lutz Donnerhacke
@ 2006-04-12 15:04 ` Gautier
2006-04-12 17:00 ` Robert A Duff
` (2 subsequent siblings)
4 siblings, 0 replies; 9+ messages in thread
From: Gautier @ 2006-04-12 15:04 UTC (permalink / raw)
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!
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Quicksort algorithm in ada
2006-04-12 13:43 Quicksort algorithm in ada Thomas Krueger
2006-04-12 14:22 ` Lutz Donnerhacke
2006-04-12 15:04 ` Gautier
@ 2006-04-12 17:00 ` Robert A Duff
2006-04-12 18:06 ` Georg Bauhaus
2006-04-19 16:35 ` Jeffrey R. Carter
4 siblings, 0 replies; 9+ messages in thread
From: Robert A Duff @ 2006-04-12 17:00 UTC (permalink / raw)
"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
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Quicksort algorithm in ada
2006-04-12 13:43 Quicksort algorithm in ada Thomas Krueger
` (2 preceding siblings ...)
2006-04-12 17:00 ` Robert A Duff
@ 2006-04-12 18:06 ` Georg Bauhaus
2006-04-12 18:11 ` Georg Bauhaus
2006-04-19 16:35 ` Jeffrey R. Carter
4 siblings, 1 reply; 9+ messages in thread
From: Georg Bauhaus @ 2006-04-12 18:06 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Quicksort algorithm in ada
2006-04-12 13:43 Quicksort algorithm in ada Thomas Krueger
` (3 preceding siblings ...)
2006-04-12 18:06 ` Georg Bauhaus
@ 2006-04-19 16:35 ` Jeffrey R. Carter
4 siblings, 0 replies; 9+ messages in thread
From: Jeffrey R. Carter @ 2006-04-19 16:35 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 9+ messages in thread