DAA: Bead Sort Algorithm

Bead Sort Algorithm

The bead sort is also known as the gravity sort algorithm. The algorithm is based on the natural phenomena of gravity. The phenomenon is the falling of things under gravity.

Let us understand it with the help of the below illustration:

Beads are represented here as numbers in the given image.

The algorithm is to settle down all the beads one by one. So in this way the maximum number of beads will be at bottom and the lesser numbers following up in the same vertical level. Likewise, the smallest element will be at the top and the largest element will be at bottom, hence, array is sorted.

       Let us look at how we will sort (3, 4, 1, 2) using bead sort -

C++ code:

 #include <vector>
 #include <iostream>
 #include <bits/stdc++.h>
 using namespace std;
 // BeadSort algorithm function
 void beadSort(vector<int>& arr)
 {
     // find maximum element in vector
     auto max = *std::max_element(std::begin(arr), std::end(arr));
     // declare beads vector for sorting
     vector<unsigned char> beads(max * arr.size(), 0);
     // initialize the beads accordingly
     for (auto i = 0; i < arr.size(); i++)
         for (auto j = 0; j < arr[i]; j++)
             beads[i * max + j] = 1;
     // Use gravity to let beads fall
     for (auto j = 0; j < max; j++) {
         int sum = 0;
         // assign beads for each post
         for (auto i = 0; i < arr.size(); i++) {
             sum += beads[i * max + j];
             beads[i * max + j] = 0;
         }
         // Use gravity to bring beads down
         for (auto i = arr.size() - sum; i < arr.size(); i++)
             beads[i * max + j] = 1;
     }
     // put sorted beads back into vector
     for (auto i = 0; i < arr.size(); i++) {
         for (auto j = 0; j < max && beads[i * max + j]; ++j) // Inner loop
             arr[i] = j + 1;
     }
 }
 int main()
 {
     // initialize vector
     vector<int> arr = { 23, 2, 12, 54, 90, 102, 32 };
     int n = sizeof(arr) / sizeof(arr[0]);
     // reserve static vector for optimal performance gain
     arr.reserve(n);
     // Print vector before sorting
     cout << "Before sorting" << endl;
     for (auto const& i : arr)
         cout << i << " ";
     cout << endl;
     beadSort(arr);
     // Print vector after sorting
     cout << "After sorting" << endl;
     for (auto const& i : arr)
         cout << i << " ";
     cout << endl;
     // Free memory space of vector
     arr.shrink_to_fit();
 } 

C code:

 #include <stdio.h>
 #include <stdlib.h>
 #define BEAD(i, j) beads[i * max + j]
 void bead_sort(int* a, int len)
 {
     int i, j, max, sum;
     unsigned char* beads;
     for (i = 1, max = a[0]; i < len; i++)
         if (a[i] > max)
             max = a[i];
     beads = calloc(1, max * len);
     /* mark the beads */
     for (i = 0; i < len; i++)
         for (j = 0; j < a[i]; j++)
             BEAD(i, j) = 1;
     for (j = 0; j < max; j++) {
         /* count how many beads are on each post */
         for (sum = i = 0; i < len; i++) {
             sum += BEAD(i, j);
             BEAD(i, j) = 0;
         }
         /* mark bottom sum beads */
         for (i = len - sum; i < len; i++)
             BEAD(i, j) = 1;
     }
     for (i = 0; i < len; i++) {
         for (j = 0; j < max && BEAD(i, j); j++)
             ;
         a[i] = j;
     }
     free(beads);
 }
 int main()
 {
     int i, x[] = { 23, 2, 12, 54, 90, 102, 32 };
     int len = sizeof(x) / sizeof(x[0]);
     printf("Before sorting: ");
     for(int i=0;i<len;i++)
     printf("%d ",x[i]);
     bead_sort(x, len);
     printf("\n");
     printf("After sorting: ");
     for (i = 0; i < len; i++)
         printf("%d ", x[i]);
     return 0;
 } 

Output:

 Before sorting: 23 2 12 54 90 102 32
 After sorting: 2 12 23 32 54 90 102