Intel® Moderncode for Parallel Architectures
Support for developing parallel programming applications on Intel® Architecture.
Announcements
This community is designed for sharing of public information. Please do not share Intel or third-party confidential information here.

## Parallel Quicksort version 1.01 ...

Novice
102 Views

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

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

Sincerely
Amine Moulay Ramdane.

Novice
102 Views

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)