Slug #96: sort is too slow - CoCoA-5 - CoCoA Project

Slug #96

sort is too slow

Added by John Abbott about 12 years ago. Updated almost 3 years ago.

Status:

New

Priority:

Normal

Assignee:

John Abbott

Category:

Incomplete function

Target version:

CoCoA-5.?.?

Start date:

01 Mar 2012

Due date:

% Done:

Estimated time:

15.00 h

Spent time:

2.10 h

Description

Sorting is achieved by $list.QuickSort.

Unfortunately it should be called SlowSort. Complexity seems to be quadratic -- why??? The cause may be a bad impl in list.cpkg5, or a problem in the interpreter.

Try the following code; then again but halving or doubling the value of N.

N := 20000;
L := [Rand(-N,N) | I In 1..N];
T1 := CpuTime();
Sort(ref L);
T2 := CpuTime();
PrintLn "Sorted in time ", DecimalStr(T2-T1);

At least C5 is better than C4 where QuickSort appeared to be almost cubic!!!

Related issues

History

#1 Updated by John Abbott about 12 years ago

It seems highly likely that copies are being made of the list being sorted. Here is my justification:

I created a list with 40000 random integers, and then called $list.QuickSort1 to sort just the first 10000 elements (I also sorted just the last 10000 elements to confirm that it took about the same time). The time taken was about 10.8s on my computer. Compare this to 3.8s which is the time needed to sort a list of length 10000 (full of random integers). I conclude that somewhere copies are being made of the entire list even though it is passed by reference.

Anna suspects that it may be related to issue #31.