Groups | Search | Server Info | Keyboard shortcuts | Login | Register

Groups > comp.programming.threads > #1058

Re: Parallel bucket sort was updated to version 1.01...

Cross-posted to 2 groups.

Show key headers only | View raw

Hello,

I have updated parallel bucketsort to versin 1.02..


Now you can sort in both ascending and descending order,
and i have changed a little bit the interface , now
if you want to sort in ascending order you have to call
the bucketsort method with ctAscending , and if you
want to sort in descending  order call it with ctDescending
like this

myobj.bucketsort(tab,comp,comp1,ctAscending);
// use ctAscending or CtDescending.



You can download parallel bucketsort from:

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




Thank you,
Amine Moulay Ramdane

"aminer" <aminer@videotron.ca> wrote in message 
news:k2d8gq$sca$1@dont-email.me...
>
> Hello,
>
> 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(Item1:Pointer): 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[i]).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[i]).mystring,' ');
> end;
>
> for i := 0 to HIGH(Tab) do freeandnil(TStudent(tab[i]));
>
> setlength(tab,0);
> myobj.free;
>
> end.
>
>
> You can download parallel bucketsort 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 bucket sort was updated to version 1.01... "aminer" <aminer@videotron.ca> - 2012-09-07 11:48 -0500
  Re: Parallel bucket sort was updated to version 1.01... "aminer" <aminer@videotron.ca> - 2012-09-10 14:05 -0500

csiph-web