Parallel Quicksort has been updated to version 1.06

[aminer]

Hello,

Parallel Quicksort has been updated to version 1.06, i have stress tested it
and it didn't show any problem.


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.

It gives:


= 2 (2T(n/4) +n/2) + n
=4T(n/4)+n+n
=4T(n/4)+2*n
=4 (2T(n/8) +n/4) + 2*n
=8T(n/8)+n+2n
=8T(n/8)+3*n
=2k T(n/2^k) + k*n

We want:


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)

But the complexity of the quicksort in the worst case is:


T(n)= n + T(n-1)

it gives:


T(n) = n + (n-1) + T(n-2)
T(n) = n + (n-1) + (n-2)+ T(n-3)
T(n) = 1 + 2+ 3+.+N
T(n) = O(n^2) // n power of 2


You can download parallel quicksort from:

http://pages.videotron.com/aminer/


Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,


The median-of-three  that i have implemented in Parallel Quicksort,
avoids the worst case performance.


Thank you,
Amine Moulay Ramdane.