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.06
 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 2 2012, 5:31 pm
Newsgroups: comp.lang.pascal.misc
From: "aminer" <ami...@toto.com>
Date: Fri, 2 Nov 2012 16:35:18 -0500
Local: Fri, Nov 2 2012 5:35 pm
Subject: Parallel Quicksort has been updated to version 1.06
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
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
?
?

Thank you,
Amine Moulay Ramdane.
?
?