how to implement bucket sort?

Question

I m new to programming and I need to implement bucket sort in c. I need to use linked list for bucket sort. My confusion is how will I create an array of linked lists and how will I insert values into the linked list according to their values. other programs which I found on the net are too complex.i am not able to understand them.so can someone please help me

Sure, [read a good book](http://stackoverflow.com/questions/562303/the-definitive-c-book-guide-and-list). — , Dec 14 '13 at 18:49

Deepak · Accepted Answer · 2013-12-15T18:05:56.147

start first by creating a linked list with all the functions required like add, remove, swap etc and then add all unsorted data into it and then pass your list to the function which actually sorts the list. and use your functions like swap etc to exchange objects(ints, chars or strings whatever your are sorting).

It can be a little confusing if you are new to c. but start first and then you can paste some code for us to look at and help but don't expect someone is going to give you complete solution.

also this is a good explanation of bucket sort this might help you understanding what you need to implement.

http://www.youtube.com/watch?annotation_id=annotation_508951&feature=iv&src_vid=Iiuqrns0Gwk&v=ovAfqUafjAA

and this is can help you understanding the implementation of linked list in c http://spicemind.com/notes/c/c-linked-list-implementation/

==============================================================================

yes you can create a array of linked list suppose you implemented a linked list :

struct linkedlist
{
  //implementation of linked list.
};

then inside main you can declare a linked list:

struct linkedlist mylist1;

and to create an array of linkedlist inside main:

struct linkedlist[10] mylist2;

to access different section of this array of linked list: mylist2[0].data = x; //suppose you have a int type called data inside linked list where you store you data. and so on

do i need to make an array of linked list?? because the main aim of bucket sort is to divide the numbers into appropriate buckets. which means i will be needing ten buckets 0-9.how can i create an array of linked list? — user3102859, Dec 15 '13 at 17:11

score 0 · Answer 2 · answered Dec 14 '13 at 19:11

The most common variant of bucket sort operates on a list of n numeric inputs between zero and some maximum value M and divides the value range into n buckets each of size M/n. If each bucket is sorted using insertion sort, the sort can be shown to run in expected linear time (where the average is taken over all possible inputs). However, the performance of this sort degrades with clustering; if many values occur close together, they will all fall into a single bucket and be sorted slowly.

Explanation Video for Bucket Sort

how to implement bucket sort?

2 Answers2