A

#### aminer

Bucket sort is not a sorting algorithm itself, rather it is a

procedure for partitioning data to be sorted using some given

sorting algorithm-a "meta-algorithm" so to speak.

Bucket sort will be better, when elements are uniformly distributed

over an interval [a, b] and buckets have not significantly different

number of elements.

bucketsort sequential computational complexity using quicksort is

= p × (n/p) log(n/p) = n log(n/p)

bucket sort parallel computational complexity using quicksort

= (n/p) log(n/p)

Parallel BucketSort gave me also 3x scaling when sorting strings on a

quad cores, it scales better than my parallel quicksort and it can be

much faster than my parallel quicksort.

I have thought about my parallel quicksort , and i have found

that parallelquicksort is fine but the problem with it is that the

partition function is not parallelizable , so i have thought about this

and i have decided to write a parallel BucketSort,and this parallel

bucketsort can give you much better performance than parallel quicksort

when sorting 100000 strings or more, just test it yourself and see,

parallel bucketsort can sort just strings at the moment, and it can use

quicksort or mergesort, mergesort is faster.

I have updated parallel bucketsort to version 1.01 , i have

changed a little bit the interface, now you have to pass

to the bucketsort method three parameters: the array,

a TSortCompare function and a TSortCompare1 function.

Here is a small example in Object Pascal:

program test;

uses parallelbucketsort,sysutils,timer;

type

TStudent = Class

public

mystring:string;

end;

var tab:Ttabpointer;

myobj:TParallelSort;

student:TStudent;

i,J:integer;

a:integer;

function comp1(Item1ointer): string;

begin

result:=TStudent(Item1).mystring ;

end;

?

function comp(Item1, Item2: Pointer): integer;

begin

if TStudent(Item1).mystring > TStudent(Item2).mystring

then

begin

result:=1;

exit;

end;

if TStudent(Item1).mystring < TStudent(Item2).mystring

then

begin

result:=-1;

exit;

end;

?

if TStudent(Item1).mystring = TStudent(Item2).mystring

then

begin

result:=0;

exit;

end;

end;

?

begin

myobj:=TParallelSort.create(1,ctQuicksort); // set to the number of cores...

setlength(tab,1000000);

?

for i:=low(tab) to high(tab)

do

begin

student:=TStudent.create;

student.mystring:= inttostr(i);

tab[high(tab)-i]:= student;

end;

?

HPT.Timestart;

myobj.bucketsort(tab,comp,comp1);

//myobj.qsort(tab,comp);

writeln('Time in microseconds: ',hpt.TimePeriod);

?

writeln;

writeln('Please press a key to continu...');

readln;

for i := LOW(tab) to HIGH(Tab)-1

do

begin

if tstudent(tab

*).mystring > tstudent(tab[i+1]).mystring*

then

begin

writeln('sort has failed...');

halt;

end;

end;

for i := LOW(tab) to HIGH(Tab)

do

begin

writeln(TStudent(tab

then

begin

writeln('sort has failed...');

halt;

end;

end;

for i := LOW(tab) to HIGH(Tab)

do

begin

writeln(TStudent(tab

*).mystring,' ');*

end;

for i := 0 to HIGH(Tab) do freeandnil(TStudent(tabend;

for i := 0 to HIGH(Tab) do freeandnil(TStudent(tab

*));*

setlength(tab,0);

myobj.free;

end.

You can download parallel bucketsort from:

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

Thank you,

Amine Moulay Ramdane.setlength(tab,0);

myobj.free;

end.

You can download parallel bucketsort from:

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

Thank you,

Amine Moulay Ramdane.