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

Groups > comp.programming.threads > #1217

Re: Parallel Quicksort has been updated to version 1.06 ...

Cross-posted to 2 groups.

Show all headers | View raw

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

Back to comp.programming.threads | Previous | Next — Previous 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