Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Intel Community
- Software
- Software Development Topics
- Intel® Moderncode for Parallel Architectures
- Parallel Quicksort version 1.01 ...

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

aminer10

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-13-2010
12:55 PM

27 Views

Parallel Quicksort version 1.01 ...

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.

Link Copied

1 Reply

aminer10

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-13-2010
01:03 PM

27 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)

You can download parallel quicksort from:

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

Sincerely,

Amine Moulay Ramdane.

Topic Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page

For more complete information about compiler optimizations, see our Optimization Notice.