flat assembler
Message board for the users of flat assembler.

Index > Heap > GPUSort better than CPUSort?

Goto page Previous  1, 2
Author
Thread Post new topic Reply to topic
MCD



Joined: 21 Aug 2004
Posts: 604
Location: Germany
MCD
The_Grey_Beast wrote:
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

-||__/
.|+-~
.|| ||
Post 13 Mar 2008, 16:45
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.