Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #1216

Parallel Quicksort has been updated to version 1.06 ...

Cross-posted to 2 groups.

Show key headers only | View raw

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.
?
? 

Back to comp.programming.threads | Previous | Next — Next in thread | Find similar

Thread

Parallel Quicksort has been updated to version 1.06 ... "aminer" <aminer@toto.com> - 2012-11-02 16:34 -0500
  Re: Parallel Quicksort has been updated to version 1.06 ... "aminer" <aminer@toto.com> - 2012-11-02 16:57 -0500

csiph-web