Sorting speed improvement

[Jaime Torres]

> 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 :))

First. I know that the algorithm is a radix sort. When I was playing with
the Spectrum,
18 years ago, I implemented this algorithm the first time in basic.

Second. In the University, I've learned two complexity notations:
O(....)   o in uppercase, that talks about the higher exponent in the
complexity
and
o(.....)  o in lowercase, that talks about all the factors in the
complexity.

In that way, an algorith with o(n^2*k) or o(3*n^2+50) is O(n^2) if k is
constant.
In this notation, you are talking about an o(n*k) complexity.
 
> 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]

Does anyone knows a sorting algorithm faster than a radix sort ?

I do not know where I said that this was "my" "program", but I will review
it 
and fix it.  And I will include links to the other pages that talk about
this algorithm.

> 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?

Not the implementation I made yesterday night. Well, I'm using the generated
QT to run KDE now, but this is not a good test.
 
> 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.

I do not know enougth of QT (still) to move the pointers, I just used the
provided methods (QT methods are easy to learn).

This implementation, therefore, is quite expensive in CPU and memory,
and, of course, is not optimal at all. It was intended as a hint.

> 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?

First. In the above notation, the Quicksort algorith is
o(n*log2(n)*k) or O(n*log2(n)).

Second. QT is using a heapSort, that is O(n*log(n)).

Third. In the Quicksort, there are String comparations, that are more
expensive than accesing an array.

Fourth. No, I do not have such an implementation, but I will do it (now that
I have again some free time) and release it under an Open Source License.

> Cheers,

Regards.
 
> -- 
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.kde.org/pipermail/kde-optimize/attachments/20030423/51be8502/attachment.htm