Groups | Search | Server Info | Keyboard shortcuts | Login | Register

Groups > comp.programming.threads > #1220

Parallel Quicksort has been updated to version 1.07

Cross-posted to 2 groups.

Show all headers | View raw

Hello,

Skybuck Flying wrote:

>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 ;)


Parallel Quicksort has been updated to version 1.07, i have stress tested it
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.

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)



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.07 "aminer" <aminer@toto.com> - 2012-11-03 18:21 -0500
  Re: Parallel Quicksort has been updated to version 1.07 Gerald Breuer <Gerald.Breuer@googlemail.com> - 2012-11-04 04:42 +0100

csiph-web