Sorting speed improvement

[Eray Ozkural]

On Wednesday 23 April 2003 11:16, Jaime Torres wrote:
> Hello,
>
> 	Yesterday I implemented an improved sorting algorithm (Postman Sort)
> in the
> QStringList class that I'm using right now. This algorithm is O(n) !!!!
>

Some points:

1) Postman's sort is radix sort with "string" keys, therefore it has 
complexity O(n*k) where k is the max. length of the string. Claiming O(n) 
would not be accurate IMO. O(n) would be true if and only if the number of 
digits in the key, here corresponding to the length of string, were constant 
which is not the case here. Note that the real complexity analysis is 
slightly more complex than that (I will do it if you like but it's 
unnecessary, same as radix sort. See MIT's "Introduction to Algorithms" 
textbook if you are curious. I have it on my desk now :))

2) The above point is reflected in your code. There are three loops. Counts 
are max_len, 256, length(B[k]) which is O( max_len * length(A) ), where B is  
the array of intermediate lists and A is the input list . You should also be 
overly skeptical when somebody dubs "his algorithm" "WORLD'S FASTEST SORTING 
PROGRAM" which is in fact just an instance of a well known sorting technique. 
I would be much more modest with the naming!!!!! [His "whitepaper" is faaar 
from modest while his technique is almost trivial, interesting attitude]

3) Your implementation seems to be OK but you have to be skeptical when you 
are implementing a sorting algorithm!  Did you actually test it?

4) Your implementation might have some hidden costs. Are you sure this line 
will result in constant time?:
    lst[(*it).at(i)].append(*it); 
Qt does have "value sharing" but I would double-check such things. It looks 
like you are assuming you are just moving around pointers, right? If these 
calls induce memory calls they will be overly expensive.

Also, w.r.t. point 1, quicksort with ordinary string comparison would really 
have O(n*logn*k) worst case running time complexity... Is that the case 
currently in QStringList? If so, I strongly suggest that this algorithm be 
made available as an optional code in Qt, maybe something like 
QStringList::fastSortASCII(). Please license it under BSD after you test it! 
It would be nice if you could write a test suite code with assert()'s spewed 
out all over the place.  You should already have such a thing, no?

Cheers,

-- 
Eray Ozkural (exa) <erayo at cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara  KDE Project: http://www.kde.org
www: http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C