Groups > comp.programming.threads > #1217

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

Path	csiph.com!usenet.pasdenom.info!gegeweb.org!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail
From	"aminer" <aminer@toto.com>
Newsgroups	comp.programming.threads, comp.programming
Subject	Re: Parallel Quicksort has been updated to version 1.06 ...
Date	Fri, 2 Nov 2012 16:57:54 -0500
Organization	A noiseless patient Spider
Lines	85
Message-ID	<k71fe0$4v5$2@dont-email.me> (permalink)
References	<k71e17$s6e$2@dont-email.me>
Injection-Date	Fri, 2 Nov 2012 21:54:08 +0000 (UTC)
Injection-Info	mx04.eternal-september.org; posting-host="c43ca82f9e8d62a602307fe9d2e9b807"; logging-data="5093"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/WlV7n+9qNwiPPTpPv5Yww"
X-MimeOLE	Produced By Microsoft MimeOLE V6.00.2900.6157
X-RFC2646	Format=Flowed; Response
X-Newsreader	Microsoft Outlook Express 6.00.2900.5931
Cancel-Lock	sha1:dKZj/6TQ3VAPkxkYvVieowe8+Rg=
X-Priority	3
X-MSMail-Priority	Normal
Xref	csiph.com comp.programming.threads:1217 comp.programming:2441

Cross-posted to 2 groups.

Show key headers only | 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