Skybuck Flying wrote:
Parallel Quicksort has been updated to version 1.07, i have stress tested it
>You sure about that, picking a pivot seems fundamentally broken.
>Here is an example for you to test:
>1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> Try sorting that with any quicksort algorithm and let me know how it goes
>for ya ;)
and it didn't show any problem.
In this new version i have changed the partition() function and also i have
used the median of three implementation so that it avoids the worst case
performance. (including the kind .Skybuck Flying was talking about).
Parallel Quicksort is an implementation of the median-of-three that gives
almost 10% better speed.
Parallel Quicksort gave me almost 3x scaling when sorting strings and
integers on a quad cores,
and now in version 1.06 you can use it also in an hybrid manner with
mergsort, just by passing
ctmergesort to the constructor it will give 10% better speed.
And as you know , Quicksort is a divide and conquer algorithm that have the
following best case performance:
T(n) = T(n/2) + T(n/2) + O(n)
= 2T(n/2) + (n)
cause it take O(n) for the partition part.
= 2 (2T(n/4) +n/2) + n
=4 (2T(n/8) +n/4) + 2*n
=2k T(n/2^k) + k*n
n/2k = 1
n = 2k
log n = k
so the reccurence equation gives:
= nT(1) +n*log(n)
= n+ (n * log(n))
So the quicksort complexity in the best case is:
n * log(n)
You can download parallel quicksort from:
Amine Moulay Ramdane.