Bead Sort: An algorithm that works faster with hardware implementation

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
{
int i, j, max, sum;
for (i = 1, max = a[0]; i < len; i++)
if (a[i] > max) max = a[i];
beads = calloc(1, max * len);
for (i = 0; i < len; i++)
for (j = 0; j < a[i]; j++)
for (j = 0; j < max; j++) {
/* count how many beads are on each post */
for (sum = i = 0; i < len; i++) {
}
/* 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;
}
}
int main()
{
int i, x[] = {5, 3, 1, 7, 4, 1, 1, 20};
int len = sizeof(x)/sizeof(x[0]);
for (i = 0; i < len; i++)
printf("%d\n", x[i]);
return 0;
}


C++


#include <vector>
#include <iostream>
using namespace std;
// Part of Cosmos by OpenGenus Foundation
// function to perform the above algorithm
{
// 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);
for (size_t i = 0; i < a.size(); ++i)
for (int j = 0; j < a[i]; ++j)
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)
{
}
for (size_t i = a.size() - sum; i < a.size(); ++i)
}
// 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};
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
MARKED,
NOT_MARKED,
}
public static void main(String[] args) {
int[] arrayToSort = new int[]{4, 1, 6, 2, 40, 5, 3, 8, 7};
}
public static int[] beadSort(int[] arr) {
int max = 0;
for (int anArr : arr) {
if (anArr > max) {
max = anArr;
}
}
//Set up abacus
int[] levelcount = new int[max];
for(int i = 0; i < max; i++) {
levelcount[i] = 0;
for(int j = 0; j < arr.length; j++) {
}
}
for (int anArr : arr) {
int num = anArr;
for (int j = 0; num > 0; j++, num--) {
}
}
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
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 */
//
//  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))
for i in 0..<n {
for j in 0..<m {
if j < array[i] {
beads[i * m + j] = 1
}
}
}
for j in 0..<m {
var sum = 0
for i in 0..<n {
sum += Int(beads[i * m + j])
beads[i * m + j] = 0
}
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
}
}


Congratulations, you understand Bead Sort / Gravity Sort

Alexa Ryder

Hi, I am creating the perfect textual information customized for learning. Message me for anything.