Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Broken Quicksort algorithm for Sort.array #8444

Closed
vicuna opened this issue Jan 9, 2004 · 2 comments
Closed

Broken Quicksort algorithm for Sort.array #8444

vicuna opened this issue Jan 9, 2004 · 2 comments

Comments

@vicuna
Copy link

vicuna commented Jan 9, 2004

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

@vicuna
Copy link
Author

vicuna commented Jan 9, 2004

Comment author: administrator

On Friday, January 9, 2004, at 07:01 PM, matias@k-bell.com wrote:

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.

-- Damien

@vicuna
Copy link
Author

vicuna commented Jan 14, 2004

Comment author: administrator

Won't fix. Documented in sort.ml. -DD 2004-01-14
This is quicksort. Fixing a bug is likely to introduce another, more severe
bug.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant