Message board for the users of flat assembler.
> Heap > GPUSort better than CPUSort?
Goto page Previous 1, 2
well I thought quicksort required linear space too, but I looked into it and the best one I could find was a logarithmic space, so it's a bit better than radix sort in that perspective. Do you know of any other better quicksort algo (I think one needs only constant space)?
Hmm, the best quicksort algorithm I know also requires logarithmic space.
This seems to be independent of how you chose the pivot value (first, last, average, median or some random element).
I find it quiet interesting, that some quicksort implementations which are very efficient in most cases like random quicksort have a worst case time-complexity of O(n^2) whilst there also exists a median quicksort which has O(n*log n) worst case time-complexity that is quiet inefficient in many cases. The later quicksort actually uses a "median of median5" algorithm which recursively takes the median of 5 adjacent elements, see http://en.wikipedia.org/wiki/Median_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22. Some of our IT proffessors showed us the proof that this only needs O(n) time and took over an hour for it, and I think he actually did it quiet fast.
MCD - the inevitable return of the Mad Computer Doggy
|13 Mar 2008, 16:45||
|Goto page Previous 1, 2
< Last Thread | Next Thread >
Copyright © 1999-2020, Tomasz Grysztar.
Powered by rwasa.