Bead Sort: An algorithm that works faster with hardware implementation

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Reading time: 15 minutes | Coding time: 10 minutes

Bead sort (also called gravity sort) is a natural sorting algorithm. Both digital and analog hardware implementations of bead sort can achieve a sorting time of O(n); however, the implementation of this algorithm tends to be significantly slower in software and can only be used to sort lists of positive integers.

This is a perfect example of an algorithm where the hardware implementation is significantly faster than the software implementation is to contrary to the common belief that software has to be faster than corresponding hardware (think of mechanical calculators)

Gravity sort has been developed by Joshua J. Arulanandham, Cristian S. Calude and Michael J. Dinneen in 2002.

Algorithm

The bead sort operation can be compared to the manner in which beads slide on parallel poles, such as on an abacus. However, each pole may have a distinct number of beads. Initially, it may be helpful to imagine the beads suspended on vertical poles.

In Step 1, put n rows of beads on m vertical poles from left to right, n is the length of the array to be sorted, m is the max num in the array.

Step 2: If we then allow the beads to fall, the rows now represent the same integers in sorted order. Row 1 contains the largest number in the set, while row n contains the smallest.

Why hardware implementation is faster?

This is because sorting step is done by Gravity (a natural physical force) and this step takes place in parrallel in one step.

In software, this step takes a minimum of m clock cycles.

Complexity

Bead sort can be implemented with four general levels of complexity, among others:

O(1): The beads are all moved simultaneously in the same time unit, as would be the case with the simple physical example above. This is an abstract complexity, and cannot be implemented in practice.
O(√N): In a realistic physical model that uses gravity, the time it takes to let the beads fall is proportional to the square root of the maximum height, which is proportional to n.
O(n): The beads are moved one row at a time. This is the case used in the analog and digital hardware solutions.
O(S), where S is the sum of the integers in the input set: Each bead is moved individually. This is the case when bead sort is implemented without a mechanism to assist in finding empty spaces below the beads, such as in software implementations.

Implementations

Implementation of Linear search algorithm in 5 languages that includes C, C++, Java, Python and Swift.

C
C++
Java
Python
Swift

C


#include <stdio.h>
#include <stdlib.h>
// Part of Cosmos by OpenGenus Foundation
void bead_sort(int *a, int len)
{
    int i, j, max, sum;
    unsigned char *beads;
#   define BEAD(i, j) beads[i * max + j]
    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[] = {5, 3, 1, 7, 4, 1, 1, 20};
    int len = sizeof(x)/sizeof(x[0]);
    bead_sort(x, len);
    for (i = 0; i < len; i++)
        printf("%d\n", x[i]);
    return 0;
}

C++


#include <vector>
#include <iostream>
using namespace std;
#define BEAD(i, j) beads[i * max + j]
// Part of Cosmos by OpenGenus Foundation
// function to perform the above algorithm
void beadSort(vector<int>& a)
{
    // Find the maximum element
    int max = a[0];
    for (size_t i = 1; i < a.size(); ++i)
        if (a[i] > max)
           max = a[i];
    // allocating memory
    vector<unsigned char> beads(max * a.size(), 0);
    // mark the beads
    for (size_t i = 0; i < a.size(); ++i)
        for (int j = 0; j < a[i]; ++j)
            BEAD(i, j) = 1;
    for (int j = 0; j < max; ++j)
    {
        // count how many beads are on each post
        int sum = 0;
        for (size_t i=0; i < a.size(); ++i)
        {
            sum += BEAD(i, j);
            BEAD(i, j) = 0;
        }
        // Move beads down
        for (size_t i = a.size() - sum; i < a.size(); ++i)
            BEAD(i, j) = 1;
    }
    // Put sorted values in array using beads
    for (size_t i = 0; i < a.size(); ++i)
    {
        int j;
        for (j = 0; j < max && BEAD(i, j); ++j);
    a[i] = j;
}

}

// driver function to test the algorithm

int main()

{

vector<int> a{5, 3, 1, 7, 4, 1, 1, 20};

beadSort(a);

cout<<"After Sorting.. "<<endl;

for (size_t i = 0; i < a.size(); ++i)

cout<<a[i]<<" ";

return 0;

}

Java


  import java.util.Arrays;
// Part of Cosmos by OpenGenus Foundation
public class BeadSort {
    private enum BeadSortStatus {
        MARKED,
        NOT_MARKED,
    }
    public static void main(String[] args) {
        int[] arrayToSort = new int[]{4, 1, 6, 2, 40, 5, 3, 8, 7};
        System.out.println(Arrays.toString(beadSort(arrayToSort)));
    }
    public static int[] beadSort(int[] arr) {
        int max = 0;
        for (int anArr : arr) {
            if (anArr > max) {
                max = anArr;
            }
        }
        //Set up abacus
        BeadSortStatus[][] grid = new BeadSortStatus[arr.length][max];
        int[] levelcount = new int[max];
        for(int i = 0; i < max; i++) {
            levelcount[i] = 0;
            for(int j = 0; j < arr.length; j++) {
                grid[j][i] = BeadSortStatus.NOT_MARKED;
            }
        }
        //Drop the beads
        for (int anArr : arr) {
            int num = anArr;
            for (int j = 0; num > 0; j++, num--) {
                grid[levelcount[j]++][j] = BeadSortStatus.MARKED;
            }
        }
        //Count the beads
        int[] sorted=new int[arr.length];
        for(int i = 0; i < arr.length; i++) {
            int putt = 0;
            for(int j = 0; j < max && grid[arr.length - 1 - i][j] == BeadSortStatus.MARKED; j++) {
                putt++;
            }
            sorted[i] = putt;
        }
        return sorted;
    }
}

Python


  # Part of Cosmos by OpenGenus Foundation
def bead_sort(obj):
    if all([type(x) == int and x >= 0 for x in obj]):
        ref = [range(x) for x in obj]  #for reference
    else:
        raise ValueError("All elements must be positive integers")
    inter = []  #for intermediate
    ind = 0  #for index
    prev = sum([1 for x in ref if len(x) > ind])  #prev for previous
    while prev:
        inter.append(range(prev))
        ind += 1
        prev = sum([1 for x in ref if len(x) > ind])
    ind = 0
    prev = sum([1 for x in inter if len(x) > ind])
    out = []
    while prev:
        out.append(prev)
        ind += 1
        prev = sum([1 for x in inter if len(x) > ind])
    out = out[::-1]
    return out

Swift


  /* Part of Cosmos by OpenGenus Foundation */
//
//  bead_sort.swift
//  Created by DaiPei on 2017/10/12.
//
import Foundation
func beadSort(_ array: inout [Int]) {
    let n = array.count
    var m = Int.min
    // find the max value
    for i in 0..<n {
        if array[i] > m {
            m = array[i]
        }
    }
    var beads = [Int8](repeatElement(0, count: m * n))
    // put beads
    for i in 0..<n {
        for j in 0..<m {
            if j < array[i] {
                beads[i * m + j] = 1
            }
        }
    }
    for j in 0..<m {
        // count beads
        var sum = 0
        for i in 0..<n {
            sum += Int(beads[i * m + j])
            beads[i * m + j] = 0
        }
        // move down beads
        for i in n - sum..<n {
            beads[i * m + j] = 1
        }
    }
    // put sorted value in array using beads
    for i in 0..<n {
        var j = 0
        while j < m {
            if beads[i * m + j] == 0 {
                break
            }
            j += 1
        }
        array[i] = j
    }
}