[erlang-questions] Bucket Sort

tonakai <>
Thu May 21 12:24:17 CEST 2009


On Thu, May 21, 2009 at 3:33 AM, Colm Dougan <> wrote:
>
> On Thu, May 21, 2009 at 12:20 AM, tonakai <> wrote:
> > Hi,
> > i am a erlang newbie and trying to implement bucket sort, but i am stuck at
> > the beginning because I can't figure out a way to divide the list into small
> > buckets, i try to use accumulators but number of buckets is not fixed, i
> > think i need to find a way to populate lists of lists.
> > also i am thinking for concurrent version of it, but its also same problem,
> > i need to send the number to the correct bucket (process).
> > any ideas?
>
> Can you give an example of the type of data you are working with?

I am working with simple integers for now.
>
> Typically the 'dict' module is useful for grouping things, e.g. :
>
>   List =
>   [1,2,3,3,4,4,4,5,6,6,7,8,9,10,10,11],
>
>   D1 =
>   lists:foldl(
>       fun(El, Acc) ->
>           Bucket = (3 * (El div 3)),
>           dict:append(Bucket, El, Acc)
>       end,
>       dict:new(),
>       List
>   ),
>
>   io:format("~p~n", [dict:to_list(D1)]),
>
>
> Colm

Thanks it works :)

i modify your code to divide the list to bucket:
%%N is the number of buckets and Max is the maximum limit for the integers in
%%the list, so that i can calculate the range of the buckets.
divide(List, N, Max) -> lists:foldl(
    fun(E1, Acc) ->
    Bucket = ((Max div N)*(E1 div (Max div N))),
    dict:append(Bucket, E1, Acc)
    end,
    dict:new(), List).

thanks again, i will work more and let you know if something goes wrong....

--
Aykut Soysal
Pod Palackehova Vrchem a05-517 Brno

http://aykutsoysal.com
+420774281226



More information about the erlang-questions mailing list