Parallel bucketsort was updated to version 1.01...

Discussion in 'Java' started by aminer, Sep 7, 2012.

  1. aminer

    aminer Guest

    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).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).mystring,' ');
    end;

    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.
     
    aminer, Sep 7, 2012
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. desktop

    Bucketsort?

    desktop, Sep 17, 2007, in forum: C++
    Replies:
    11
    Views:
    1,039
    Victor Bazarov
    Sep 18, 2007
  2. V Green
    Replies:
    0
    Views:
    861
    V Green
    Feb 5, 2008
  3. PA Bear [MS MVP]
    Replies:
    0
    Views:
    971
    PA Bear [MS MVP]
    Feb 5, 2008
  4. aminer
    Replies:
    3
    Views:
    340
    aminer
    Sep 7, 2012
  5. aminer
    Replies:
    0
    Views:
    356
    aminer
    Sep 7, 2012
Loading...

Share This Page