Re: Parallel quicksort
On Sat, 15 May 2010, Arne Vajh?j wrote:
On 15-05-2010 19:47, markspace wrote:
Arne Vajh?j wrote:
} else {
ThreadSortHelp h1 = new ThreadSortHelp(n1, r, ia, depth + 1, tdepth);
ThreadSortHelp h2 = new ThreadSortHelp(l, n2, ia, depth + 1, tdepth);
Just a thought: Why spawn two threads here? You already have one thread
running (the current one). Spawn one thread (proabaly on the larger span
between pivot and start/end) and sort the other bit recursively in the
current thread. Then just wait on the other thread after you're done
with the recursive sort.
It may be more efficient. But I like the symmetric approach of
this code.
This would be an ideal use for the JSR-166y fork-join framework, which
lets you express the two branches symmetrically, but have the executed
without unnecessary thread creations. If you can't wait for java 7, get it
from Doug Lea:
http://gee.cs.oswego.edu/dl/concurrency-interest/index.html
However, I played around with this myself a while ago, and I'm not sure
the whole idea is a great one. Quicksorts are god-awful at sorting many
real world types of data. If a list is already sorted, then quicksort
degenerates into a bubble sort. That's N^2 performance. And pre-sorted
data is pretty common so you're likely to hit this issue often.
Not quite correct.
Quicksort degenerate into O(n^2) for sorted data *if* the first
or last element is used as pivot.
My code used the middle element.
For the very same reason.
That works super for sorted data.
Ofcourse there still exists some orders that degenerate
into O(n^2), but they are not very likely (unlike the already
sorted order).
All correct. But for real-world data, even tweakedd quicksorts are
routinely beaten by adaptive sorts like Timsort. Of course, what's
relevant right here is that quicksort can be parallelised - i'm not aware
that Timsort can be, and i have no idea about any other adaptive sorts.
tom
--
eviscerated by obfuscation