* Re: Quicksort
[not found] <01bdbaef$d13c9340$86eba8c2@j.couston>
@ 1998-07-29 0:00 ` Hans-Malte Kern
1998-07-31 0:00 ` Quicksort Michael F Brenner
1998-07-29 0:00 ` Quicksort Johan Stäring
1998-07-30 0:00 ` Quicksort Ellis E Hardin
2 siblings, 1 reply; 4+ messages in thread
From: Hans-Malte Kern @ 1998-07-29 0:00 UTC (permalink / raw)
To: Jamie
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
--
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Quicksort
[not found] <01bdbaef$d13c9340$86eba8c2@j.couston>
1998-07-29 0:00 ` Quicksort Hans-Malte Kern
@ 1998-07-29 0:00 ` Johan Stäring
1998-07-30 0:00 ` Quicksort Ellis E Hardin
2 siblings, 0 replies; 4+ messages in thread
From: Johan Stäring @ 1998-07-29 0:00 UTC (permalink / raw)
To: Jamie
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 ||
========================================================================
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Quicksort
[not found] <01bdbaef$d13c9340$86eba8c2@j.couston>
1998-07-29 0:00 ` Quicksort Hans-Malte Kern
1998-07-29 0:00 ` Quicksort Johan Stäring
@ 1998-07-30 0:00 ` Ellis E Hardin
2 siblings, 0 replies; 4+ messages in thread
From: Ellis E Hardin @ 1998-07-30 0:00 UTC (permalink / raw)
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>.
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Quicksort
1998-07-29 0:00 ` Quicksort Hans-Malte Kern
@ 1998-07-31 0:00 ` Michael F Brenner
0 siblings, 0 replies; 4+ messages in thread
From: Michael F Brenner @ 1998-07-31 0:00 UTC (permalink / raw)
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;
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~1998-07-31 0:00 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <01bdbaef$d13c9340$86eba8c2@j.couston>
1998-07-29 0:00 ` Quicksort Hans-Malte Kern
1998-07-31 0:00 ` Quicksort Michael F Brenner
1998-07-29 0:00 ` Quicksort Johan Stäring
1998-07-30 0:00 ` Quicksort Ellis E Hardin
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox