Project

General

Profile

Bug #544

sorted gives wrong answer sometimes

Added by John Abbott about 10 years ago. Updated about 10 years ago.

Status:
Closed
Priority:
High
Assignee:
John Abbott
Category:
Incomplete function
Target version:
CoCoA-5.1.0 Easter14
Start date:
28 Apr 2014
Due date:
% Done:

100%

Estimated time:
4.00 h
Spent time:
3.75 h

Description

L1:=[20, 73, 89, 1, 74, 70, 46, 17, 6, 28, 86, 8, 0, 16, 78, 91, 96, 68, 44, 95, 15, 30, 62, 84, 59, 85, 27, 52, 97, 87, 75, 57, 26];
L2 := sorted(L1);
L2;

The number 17 is out of order in L2.

History

#1 Updated by John Abbott about 10 years ago

The source code is in package list.cpkg5.
I found no examples of short lists; the source code uses InsertionSort for lists of length up to 32 (incl); from length 33 upwards it uses QuickSort.
So I suspect that QuickSort is buggy

#2 Updated by John Abbott about 10 years ago

As I suspected the problem seems to depend only on the relative sizes of
the list elements; here is the same example as before, but with simpler entries

L1:=[7, 73, 89, 1, 74, 70, 46, 6, 2, 10, 86, 3, 0, 5, 78, 91, 96, 68, 44, 95, 4, 30, 62, 84, 59, 85, 9, 52, 97, 87, 75, 57, 8];

#3 Updated by Anna Maria Bigatti about 10 years ago

Easier to debug (working on it)

[6, 28, 39, 1, 40, 41, 46, 7, 2, 20, 21, 3, 0, 5, 22, 23, 24, 38, 44, 37, 4, 30, 36, 35, 34, 33, 27, 32, 31, 29, 26, 25, 10]

returns

[0, 1, 2, 3, 4, 5, 6, 10, 7, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 44, 46]

#4 Updated by Anna Maria Bigatti about 10 years ago

  • Category set to Incomplete function
  • Status changed from New to Feedback
  • Assignee set to John Abbott
  • Target version changed from CoCoA-5.1.1 Seoul14 to CoCoA-5.1.0 Easter14
  • % Done changed from 0 to 90
  • Estimated time set to 4.00 h

The problem was that after this step

    If Down > Up Then
      swap(ref L[Down], ref L[Up]);
      incr(ref Up); decr(ref Down); // now it may be Up=Down and L[Up]<Pivot
    EndIf;

we may end up with Up=Down and L[Up] never accessed.
In this case L[Up]<Pivot but the function assumed (reasonably enoough) that after the while-loop L[Up]>=Pivot.

The same happens in the second loop: we may end up with Up=Down and L[Up] never accessed. But in this case the worst that can happen is L[Up]=Pivot and this is not a problem.

#5 Updated by John Abbott about 10 years ago

I have added a new C5 test file exbugs.cocoa5 which contains a simple verification that sorted works on some randomly generated lists.

#6 Updated by John Abbott about 10 years ago

  • Status changed from Feedback to Closed
  • % Done changed from 90 to 100

Added more tests (on shorter random lists, since the code handles long and short lists separately).

Regarding the issue as fully resolved (thanks, Anna).
So closing.

Also available in: Atom PDF