The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Parallel Quicksort has been updated to version 1.07
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 1 message

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Nov 3 2012, 6:19 pm
Newsgroups: alt.comp.lang.borland-delphi
From: "aminer" <ami...@toto.com>
Date: Sat, 3 Nov 2012 18:20:13 -0500
Local: Sat, Nov 3 2012 7:20 pm
Subject: Parallel Quicksort has been updated to version 1.07
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
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)

Thank you,
Amine Moulay Ramdane.