Parallel Quicksort version 1.01 ...

aminer10 — Tue, 13 Apr 2010 19:55:55 GMT

Hello,

I have just updated parallel quicksort , now you can parallel quicksort
on 'many' cores - not just two cores - look at the new program
pqsort2.pas inside the zip

Next step i will convert pqsort2.pas program to a unit that you can import...

I am using inside pqsort2.pas the following functions:
QSortStr() , QuickSrtInt() and Merge()

Parallel quicksort version 1.01 quicksort many array parts - of your
array - in parallel using Quicksort, and after that it finally merge
them - with the merge() procedure -

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) + (n)
= 2T(n/2) + (n)

And from case 2 of Master theorem, the recurrence equation gives:

T(n) = (n lg n)

Now, i have tested mergesort in parallel , but quicksort() gives better
performance.

Note also that on Delphi parallel quicksort gave me 1.7x on two cores
- but with more optimization, delphi will give you better scalability...- .

Freepascal on the other hand gave me just 1.2x on two cores, so,
FreePascal still have to be optimized on 'some' parts for better parallel
computing...

You can download parallel quicksort from:

http://pages.videotron.com/aminer/

Sincerely
Amine Moulay Ramdane.

Parallel Quicksort version 1.01 ...

aminer10 — Tue, 13 Apr 2010 20:03:50 GMT

I wrote:
>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) + (n)

I mean T(n) = T(n/2) + T(n/2) + O(n)

= 2T(n/2) + (n)

And from case 2 of Master theorem, the recurrence equation gives:

T(n) = (n lg n)

You can download parallel quicksort from:

http://pages.videotron.com/aminer/

Sincerely,
Amine Moulay Ramdane.

topic Parallel Quicksort version 1.01 ... in Intel® Moderncode for Parallel Architectures

Parallel Quicksort version 1.01 ...

Parallel Quicksort version 1.01 ...