* Quick Sort in Rosetta Code
@ 2016-02-10 5:27 gautier_niouzes
2016-02-10 5:43 ` Jeffrey R. Carter
` (3 more replies)
0 siblings, 4 replies; 9+ messages in thread
From: gautier_niouzes @ 2016-02-10 5:27 UTC (permalink / raw)
Hello,
Couldn't not find how to reach the author of the Rosetta Code Quick Sort code
http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Ada
...but the code needs some improvement.
If you put
Wed => 99.0,
in the demo instead of
Wed => 800.0,
you get
99.00 100.00 300.00 200.00 500.00 700.00 900.00
o-O !
Additionally a generic profile compatible with Ada 2005's
Ada.Containers.Generic_Array_Sort
and a remark about its existence would be good...
Cheers
_________________________
Gautier's Ada programming
http://sf.net/users/gdemont/
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Quick Sort in Rosetta Code
2016-02-10 5:27 Quick Sort in Rosetta Code gautier_niouzes
@ 2016-02-10 5:43 ` Jeffrey R. Carter
2016-02-10 13:50 ` robin.vowels
2016-02-10 7:00 ` Leo Brewin
` (2 subsequent siblings)
3 siblings, 1 reply; 9+ messages in thread
From: Jeffrey R. Carter @ 2016-02-10 5:43 UTC (permalink / raw)
On 02/09/2016 10:27 PM, gautier_niouzes@hotmail.com wrote:
>
> Couldn't not find how to reach the author of the Rosetta Code Quick Sort code
> http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Ada
> ...but the code needs some improvement.
>
> If you put
> Wed => 99.0,
> in the demo instead of
> Wed => 800.0,
> you get
> 99.00 100.00 300.00 200.00 500.00 700.00 900.00
Not quite right. There's an implementation of Quick Sort in the PragmARCs, but
it would use insertion sort for something this short.
--
Jeff Carter
"I was in love with a beautiful blonde once, dear.
She drove me to drink. That's the one thing I'm
indebted to her for."
Never Give a Sucker an Even Break
109
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Quick Sort in Rosetta Code
2016-02-10 5:27 Quick Sort in Rosetta Code gautier_niouzes
2016-02-10 5:43 ` Jeffrey R. Carter
@ 2016-02-10 7:00 ` Leo Brewin
2016-02-10 7:14 ` Leo Brewin
2016-02-10 20:41 ` Simon Wright
3 siblings, 0 replies; 9+ messages in thread
From: Leo Brewin @ 2016-02-10 7:00 UTC (permalink / raw)
I bumped inthis problem ages ago. I think the error is that the pair of if statements in the Rosetta code
if Left < Item'Last then
Left := Index_Type'Succ(Left);
end if;
if Right > Item'First then
Right := Index_Type'Pred(Right);
end if;
should be merged as a single if statement
if Left < Item'Last and Right > Item'First then
Left := Index_Type'Succ(Left);
Right := Index_Type'Pred(Right);
end if;
This seems to fix the problem.
Cheers,
Leo
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Quick Sort in Rosetta Code
2016-02-10 5:27 Quick Sort in Rosetta Code gautier_niouzes
2016-02-10 5:43 ` Jeffrey R. Carter
2016-02-10 7:00 ` Leo Brewin
@ 2016-02-10 7:14 ` Leo Brewin
2016-02-10 10:04 ` gautier_niouzes
2016-02-10 10:16 ` gautier_niouzes
2016-02-10 20:41 ` Simon Wright
3 siblings, 2 replies; 9+ messages in thread
From: Leo Brewin @ 2016-02-10 7:14 UTC (permalink / raw)
I missed one other change, in the second last if statement the Rosetta code was
Sort(Item(Item'First..Index_Type'Pred(Right)));
I think that should be
Sort(Item(Item'First..Index_Type'Pred(Left)));
Here is the complete code
procedure Sort (Item : in out Element_Array) is
procedure Swap(Left, Right : in out Element_Type) is
Temp : Element_Type := Left;
begin
Left := Right;
Right := Temp;
end Swap;
Pivot_Index : Index_Type;
Pivot_Value : Element_Type;
Right : Index_Type := Item'Last;
Left : Index_Type := Item'First;
begin
if Item'Length > 1 then
Pivot_Index := Index_Type'Val((Index_Type'Pos(Item'Last) + 1 +
Index_Type'Pos(Item'First)) / 2);
Pivot_Value := Item(Pivot_Index);
Left := Item'First;
Right := Item'Last;
loop
while Left < Item'Last and then Item(Left) < Pivot_Value loop
Left := Index_Type'Succ(Left);
end loop;
while Right > Item'First and then Item(Right) > Pivot_Value loop
Right := Index_Type'Pred(Right);
end loop;
exit when Left >= Right;
Swap(Item(Left), Item(Right));
if Left < Item'Last and Right > Item'First then
Left := Index_Type'Succ(Left);
Right := Index_Type'Pred(Right);
end if;
end loop;
if Right > Item'First then
Sort(Item(Item'First..Index_Type'Pred(Left)));
end if;
if Left < Item'Last then
Sort(Item(Left..Item'Last));
end if;
end if;
end Sort;
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Quick Sort in Rosetta Code
2016-02-10 7:14 ` Leo Brewin
@ 2016-02-10 10:04 ` gautier_niouzes
2016-02-10 10:16 ` gautier_niouzes
1 sibling, 0 replies; 9+ messages in thread
From: gautier_niouzes @ 2016-02-10 10:04 UTC (permalink / raw)
On Wednesday, February 10, 2016 at 8:14:52 AM UTC+1, Leo Brewin wrote:
> if Right > Item'First then
> Sort(Item(Item'First..Index_Type'Pred(Left)));
> end if;
Mmmh... make no sense either: why a test with Right to prevent an out-of-range on Index_Type'Pred(Left) ?...
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Quick Sort in Rosetta Code
2016-02-10 7:14 ` Leo Brewin
2016-02-10 10:04 ` gautier_niouzes
@ 2016-02-10 10:16 ` gautier_niouzes
1 sibling, 0 replies; 9+ messages in thread
From: gautier_niouzes @ 2016-02-10 10:16 UTC (permalink / raw)
I did not dig too far into the fixing (the tricky thing is to avoid going out of range with indices) but here is, as an inspiration, a simplified case where the index type is integer, and this one is working (I've taken the C version to start with):
with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random;
--with Ada.Text_IO; use Ada.Text_IO;
procedure Qsort is
type Item_array is array(Integer Range <>) of Float;
procedure Quick_sort (a: in out Item_array) is
n: Integer:= a'Length;
i, j: Integer;
p, t: Float;
begin
if n < 2 then
return;
end if;
p := a(n / 2 + a'First);
i:= 0;
j:= n - 1;
loop
while a(i + a'First) < p loop
i:= i + 1;
end loop;
while p < a(j + a'First) loop
j:= j - 1;
end loop;
exit when i >= j;
t := a(i + a'First);
a(i + a'First) := a(j + a'First);
a(j + a'First) := t;
i:= i + 1;
j:= j - 1;
end loop;
Quick_sort(a(a'First .. a'First + i - 1));
Quick_sort(a(a'First + i .. a'Last));
end;
gen: Generator;
begin
Reset(gen);
for n in 1..100 loop
for round in 1..500 loop
declare
start: Integer:= Integer(10.0 * (Random(gen)-0.5));
a: Item_array(start .. start + n - 1);
begin
for i in a'Range loop
a(i):= Random(gen);
end loop;
Quick_sort(a);
for i in a'Range loop
-- Put_Line(Float'Image(a(i)));
if i > a'First and then a(i-1) > a(i) then
raise Program_Error; -- Buggy sorting
end if;
end loop;
end;
end loop;
end loop;
end;
_________________________
Gautier's Ada programming
http://sf.net/users/gdemont/
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Quick Sort in Rosetta Code
2016-02-10 5:43 ` Jeffrey R. Carter
@ 2016-02-10 13:50 ` robin.vowels
2016-02-10 21:39 ` Jeffrey R. Carter
0 siblings, 1 reply; 9+ messages in thread
From: robin.vowels @ 2016-02-10 13:50 UTC (permalink / raw)
On Wednesday, February 10, 2016 at 4:43:11 PM UTC+11, Jeffrey R. Carter wrote:
> On 02/09/2016 10:27 PM, g.nospam@hotmail.com wrote:
> >
> > Couldn't not find how to reach the author of the Rosetta Code Quick Sort code
> > http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Ada
> > ...but the code needs some improvement.
> >
> > If you put
> > Wed => 99.0,
> > in the demo instead of
> > Wed => 800.0,
> > you get
> > 99.00 100.00 300.00 200.00 500.00 700.00 900.00
>
> Not quite right. There's an implementation of Quick Sort in the PragmARCs, but
> it would use insertion sort for something this short.
The Rosetta Quicksort is about Quicksort,
not about Insertion Sort.
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Quick Sort in Rosetta Code
2016-02-10 5:27 Quick Sort in Rosetta Code gautier_niouzes
` (2 preceding siblings ...)
2016-02-10 7:14 ` Leo Brewin
@ 2016-02-10 20:41 ` Simon Wright
3 siblings, 0 replies; 9+ messages in thread
From: Simon Wright @ 2016-02-10 20:41 UTC (permalink / raw)
gautier_niouzes@hotmail.com writes:
> Couldn't not find how to reach the author of the Rosetta Code Quick Sort code
> http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Ada
> ...but the code needs some improvement.
>
> If you put
> Wed => 99.0,
> in the demo instead of
> Wed => 800.0,
> you get
> 99.00 100.00 300.00 200.00 500.00 700.00 900.00
Yes.
I thought this might be an interesting introduction to gnatprove (GPL
2015), and was disappointed to find that it doesn't support quantified
expressions! so you have fun writing them out longhand, which means in
the body.
I have no idea why the C code at rosettacode.org works and the Ada
doesn't, and it's not helped by having no idea what the partitioning
loop is trying to do! which makes it hard to write assertions.
void quick_sort (int *a, int n) {
int i, j, p, t;
if (n < 2)
return;
p = a[n / 2];
for (i = 0, j = n - 1;; i++, j--) {
while (a[i] < p)
i++;
while (p < a[j])
j--;
if (i >= j)
break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
quick_sort(a, i);
quick_sort(a + i, n - i);
}
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Quick Sort in Rosetta Code
2016-02-10 13:50 ` robin.vowels
@ 2016-02-10 21:39 ` Jeffrey R. Carter
0 siblings, 0 replies; 9+ messages in thread
From: Jeffrey R. Carter @ 2016-02-10 21:39 UTC (permalink / raw)
On 02/10/2016 06:50 AM, robin.vowels@gmail.com wrote:
> On Wednesday, February 10, 2016 at 4:43:11 PM UTC+11, Jeffrey R. Carter wrote:
>>
>> Not quite right. There's an implementation of Quick Sort in the PragmARCs, but
>> it would use insertion sort for something this short.
>
> The Rosetta Quicksort is about Quicksort,
> not about Insertion Sort.
Yes, of course. A simple O(N**2) sorting algorithm is faster than Quick Sort for
short arrays, so a sorting pkg for real-world use (such as the PragmARCs) should
use such an algorithm for short arrays rather than invoke the overhead of Quick
Sort.
However, the PragmARC Quick Sort is well tested; if someone wants to take out
the test for a short array and submit it to Rosetta Code, that would be fine.
--
Jeff Carter
"You tiny-brained wipers of other people's bottoms!"
Monty Python & the Holy Grail
18
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2016-02-10 21:39 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-02-10 5:27 Quick Sort in Rosetta Code gautier_niouzes
2016-02-10 5:43 ` Jeffrey R. Carter
2016-02-10 13:50 ` robin.vowels
2016-02-10 21:39 ` Jeffrey R. Carter
2016-02-10 7:00 ` Leo Brewin
2016-02-10 7:14 ` Leo Brewin
2016-02-10 10:04 ` gautier_niouzes
2016-02-10 10:16 ` gautier_niouzes
2016-02-10 20:41 ` Simon Wright
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox