You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Original bug ID: 2032 Reporter: administrator Status: closed Resolution: won't fix Priority: normal Severity: feature Category: ~DO NOT USE (was: OCaml general)
Bug description
Full_Name: Matías Giovannini
Version: 3.06
OS: Mac OS X
Submission from: 168-226-181-168.speedy.com.ar (168.226.181.168)
The partition algorithm in Sort.array implementation of Quicksort is incorrect.
The off-by-{one,two} error is masked by the subsequent application of an
insertion sort. A fix follows:
*** sort-orig.ml Fri Jan 9 14:50:53 2004
--- sort.ml Fri Jan 9 14:51:22 2004
*** 70,77 ****
while !i < !j do
while not (cmp pivot (unsafe_get arr !i)) do incr i done;
while not (cmp (unsafe_get arr !j) pivot) do decr j done;
! if !i < !j then swap arr !i !j;
! incr i; decr j
done;
(* Recursion on smaller half, tail-call on larger half )
if !j - lo <= hi - !i then begin
--- 70,76 ----
while !i < !j do
while not (cmp pivot (unsafe_get arr !i)) do incr i done;
while not (cmp (unsafe_get arr !j) pivot) do decr j done;
! if !i < !j then begin swap arr !i !j; incr i; decr j end
done;
( Recursion on smaller half, tail-call on larger half *)
if !j - lo <= hi - !i then begin
The text was updated successfully, but these errors were encountered:
The partition algorithm in Sort.array implementation of Quicksort is
incorrect.
The off-by-{one,two} error is masked by the subsequent application of
an
insertion sort. A fix follows:
Thank you for the bug report. If I remember correctly, this is
a known bug, but we don't want to fix it because it is only a
small performance bug in a module that we have declared obsolete.
Original bug ID: 2032
Reporter: administrator
Status: closed
Resolution: won't fix
Priority: normal
Severity: feature
Category: ~DO NOT USE (was: OCaml general)
Bug description
Full_Name: Matías Giovannini
Version: 3.06
OS: Mac OS X
Submission from: 168-226-181-168.speedy.com.ar (168.226.181.168)
The partition algorithm in Sort.array implementation of Quicksort is incorrect.
The off-by-{one,two} error is masked by the subsequent application of an
insertion sort. A fix follows:
*** sort-orig.ml Fri Jan 9 14:50:53 2004
--- sort.ml Fri Jan 9 14:51:22 2004
*** 70,77 ****
while !i < !j do
while not (cmp pivot (unsafe_get arr !i)) do incr i done;
while not (cmp (unsafe_get arr !j) pivot) do decr j done;
! if !i < !j then swap arr !i !j;
! incr i; decr j
done;
(* Recursion on smaller half, tail-call on larger half )
if !j - lo <= hi - !i then begin
--- 70,76 ----
while !i < !j do
while not (cmp pivot (unsafe_get arr !i)) do incr i done;
while not (cmp (unsafe_get arr !j) pivot) do decr j done;
! if !i < !j then begin swap arr !i !j; incr i; decr j end
done;
( Recursion on smaller half, tail-call on larger half *)
if !j - lo <= hi - !i then begin
The text was updated successfully, but these errors were encountered: