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

Groups > comp.programming > #2440 > unrolled thread

Parallel Quicksort has been updated to version 1.06 ...

Back to article view | Back to comp.programming

Contents

  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

#2440 — 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 
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.
?
? 

[toc] | [next] | [standalone]

#2441

Hello,


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


Thank you,
Amine Moulay Ramdane.

"aminer" <aminer@toto.com> wrote in message 
news:k71e17$s6e$2@dont-email.me...
>
> 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.
> ?
> ?
> 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web