Question

I have implemented Bucket_Sort, it successfully executed but not give desire output(all the element is not sorted), please help me out with this code

#include<iostream>

using namespace std;

struct Node{

    int data;

    Node *next;

};

int Max(int arr[], int n)

{

    int max=0;

    for (int i = 0; i < n; i++)

    {

        if (arr[i] > max)

        {

            max = arr[i];

        }

    }

    return max;

}

void Bucket_Sort(int arr[], int n)

{

    int max = Max(arr,n);

    Node *bin[max+1] = {NULL};

    Node *newnode;

    Node *temp;

    for (int i = 0; i < n; i++)

    {  

        newnode = new Node();

        newnode->data = arr[i];

        newnode->next = NULL;

        if (bin[arr[i]] == NULL)

        {   

            bin[arr[i]] = temp = newnode;

        }else

        {

            temp->next = newnode;

            temp = newnode;

            

        }

    }

    int j=0,k=0;

    while (j < max+1)

    {   Node *temp;

        if (bin[j] != NULL)

        {   temp = bin[j];

            while (temp != NULL)

            {   arr[k++] = temp->data;

                temp = temp->next;

            }

            

        }

        j++;

    }

    for (int i = 0; i < n; i++)

    {

        cout<<arr[i]<<" ";

    }

    

}

int main()

{

   int arr[] = {6,8,3,10,15,6,9,12,6,3};

   int n=10;

   Bucket_Sort(arr,n);

   return 0;

}

Answer 1

Bucket sort is a comparison sorting algorithm. It scans elements and put these into different buckets. Each bucket is sorted individually using a sorting algorithm of your choice. Here i used insertion sort for sorting the elements in the bucket.

i used static type of programming, you can modify the program by entering user defined values for sorting using cin function. The following is the source code that will helps you to sort elements using buckets. Here the bucket size is 5 and the bucket range is 10 and number of elements taken is 10. u can change them as required.

Source Code for Bucket Sorting:

#include <iostream>
#include <iomanip>
using namespace std;

#define NARRAY 10 /* array size */
#define NBUCKET 5 /* bucket size */
#define INTERVAL 10 /* bucket range */

struct Node
{
   int data;
   struct Node *next;
};

void BucketSort(int arr[]);
struct Node *InsertionSort(struct Node *list);
void print(int arr[]);
void printBuckets(struct Node *list);
int getBucketIndex(int value);

void BucketSort(int arr[])
{  
   int i,j;
   struct Node **buckets;

   /* allocate memory for array of pointers to the buckets */
   buckets = (struct Node **)malloc(sizeof(struct Node*) * NBUCKET);

   /* initialize pointers to the buckets */
   for(i = 0; i < NBUCKET;++i) {
       buckets[i] = NULL;
   }

   /* put items into the buckets */
   for(i = 0; i < NARRAY; ++i) {  
       struct Node *current;
       int pos = getBucketIndex(arr[i]);
       current = (struct Node *) malloc(sizeof(struct Node));
       current->data = arr[i];
       current->next = buckets[pos];
       buckets[pos] = current;
   }

   /* check what's in each bucket */
   for(i = 0; i < NBUCKET; i++) {
       cout << "Bucket[" << i << "] : ";
   printBuckets(buckets[i]);
       cout << endl;
   }

   /* sorting bucket using Insertion Sort */
   for(i = 0; i < NBUCKET; ++i) {
       buckets[i] = InsertionSort(buckets[i]);
   }

   /* check what's in each bucket */
   cout << "-------------" << endl;
   cout << "Bucktets after sorted" << endl;
   for(i = 0; i < NBUCKET; i++) {
       cout << "Bucket[" << i << "] : ";
   printBuckets(buckets[i]);
       cout << endl;
   }

   /* put items back to original array */
   for(j =0, i = 0; i < NBUCKET; ++i) {  
       struct Node *node;
       node = buckets[i];
       while(node) {
           arr[j++] = node->data;
           node = node->next;
       }
   }
  
   /* free memory */
   for(i = 0; i < NBUCKET;++i) {  
       struct Node *node;
       node = buckets[i];
       while(node) {
           struct Node *tmp;
           tmp = node;
           node = node->next;
           free(tmp);
       }
   }
   free(buckets);
   return;
}

/* Insertion Sort */
struct Node *InsertionSort(struct Node *list)
{  
   struct Node *k,*nodeList;
   /* need at least two items to sort */
   if(list == 0 || list->next == 0) {
       return list;
   }
  
   nodeList = list;
   k = list->next;
   nodeList->next = 0; /* 1st node is new list */
   while(k != 0) {  
       struct Node *ptr;
       /* check if insert before first */
       if(nodeList->data > k->data) {
           struct Node *tmp;
           tmp = k;
           k = k->next;
           tmp->next = nodeList;
           nodeList = tmp;
           continue;
       }

       for(ptr = nodeList; ptr->next != 0; ptr = ptr->next) {
           if(ptr->next->data > k->data) break;
       }

       if(ptr->next!=0){
           struct Node *tmp;
           tmp = k;
           k = k->next;
           tmp->next = ptr->next;
           ptr->next = tmp;
           continue;
       }
       else{
           ptr->next = k;
           k = k->next;
           ptr->next->next = 0;
           continue;
       }
   }
   return nodeList;
}

int getBucketIndex(int value)
{
   return value/INTERVAL;
}

void print(int ar[])
{  
   int i;
   for(i = 0; i < NARRAY; ++i) {
       cout << setw(3) << ar[i];
   }
   cout << endl;
}

void printBuckets(struct Node *list)
{
   struct Node *cur = list;
   while(cur) {
       cout << setw(3) << cur->data;
       cur = cur->next;
   }
}

int main(void)
{  
   int array[NARRAY] = {6,8,3,10,15,6,9,12,6,3};

   cout << "Initial array" << endl;
   print(array);
   cout << "-------------" << endl;

   BucketSort(array);
   cout << "-------------" << endl;
   cout << "Sorted array" << endl;
   print(array);
   return 0;
}