Bead Sort OR Gravity Sort Program with Explanation and Code

2025-11-19 bead sort gravity sort natural sorting algorithm python bead sort c bead sort php bead sort javascript bead sort csharp bead sort non-negative integer sorting abacus sorting method

Bead Sort (Gravity Sort) is a natural sorting algorithm inspired by how beads fall on an abacus. It works only for non-negative integers and visually simulates gravity to arrange values. Includes complete implementations in Python, C, JavaScript, PHP, and C#.

Program Explanation

What is Bead Sort?

Bead Sort (also known as Gravity Sort) is a natural sorting algorithm inspired by the way beads fall under gravity on an abacus. It works only for non-negative integers and sorts the array by simulating beads dropping down rods. Larger numbers have more beads, so they settle lower, resulting in a sorted list. Although visually interesting, Bead Sort is not used in practical systems due to high complexity and memory usage.

Steps to Solve

  1. Find the maximum value in the array.
  2. Create a grid (rows = number of elements, columns = max value).
  3. Place beads on each row equal to the element's value.
  4. Let gravity pull the beads downward (count beads in each column).
  5. Rebuild each row's value based on bead counts.
  6. Convert the bead structure back into the sorted array.

Key Points

  • Works only for non-negative integers.
  • Simulates physical gravity to sort values.
  • Time complexity can be O(n × maxValue) — expensive for large values.
  • Simple concept but impractical for most real-world uses.
  • Often used for educational and visual demonstrations.

Program Code


def bead_sort(arr):
    if any(x < 0 for x in arr):
        raise ValueError("Bead Sort works only for non-negative integers.")

    max_val = max(arr)
    beads = [[0] * max_val for _ in arr]

    for i, num in enumerate(arr):
        for j in range(num):
            beads[i][j] = 1

    for j in range(max_val):
        sum_beads = sum(beads[i][j] for i in range(len(arr)))
        for i in range(len(arr)):
            beads[i][j] = 1 if i >= len(arr) - sum_beads else 0

    for i in range(len(arr)):
        arr[i] = sum(beads[i])

arr = list(map(int, input("Enter non-negative integers: ").split()))
bead_sort(arr)
print("Sorted array:", arr)
      

#include <stdio.h>
#include <string.h>

void beadSort(int arr[], int n) {
    int max = 0;
    for (int i = 0; i < n; i++)
        if (arr[i] > max)
            max = arr[i];

    unsigned char beads[n][max];
    memset(beads, 0, sizeof(beads));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < arr[i]; j++)
            beads[i][j] = 1;

    for (int j = 0; j < max; j++) {
        int count = 0;
        for (int i = 0; i < n; i++)
            count += beads[i][j];

        for (int i = 0; i < n; i++)
            beads[i][j] = (i >= n - count) ? 1 : 0;
    }

    for (int i = 0; i < n; i++) {
        int num = 0;
        for (int j = 0; j < max; j++)
            num += beads[i][j];
        arr[i] = num;
    }
}

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter non-negative integers: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    beadSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}
      

function beadSort(arr) {
  if (arr.some(x => x < 0)) {
    console.error("Bead Sort works only for non-negative integers.");
    return;
  }

  let max = Math.max(...arr);
  let beads = Array.from({ length: arr.length }, () => Array(max).fill(0));

  arr.forEach((num, i) => {
    for (let j = 0; j < num; j++)
      beads[i][j] = 1;
  });

  for (let j = 0; j < max; j++) {
    let count = beads.reduce((sum, row) => sum + row[j], 0);

    for (let i = 0; i < arr.length; i++)
      beads[i][j] = i >= arr.length - count ? 1 : 0;
  }

  for (let i = 0; i < arr.length; i++)
    arr[i] = beads[i].reduce((a, b) => a + b);

  return arr;
}

let arr = prompt("Enter non-negative integers:").split(" ").map(Number);
console.log("Sorted array:", beadSort(arr));
      

using System;

class Program {

    static void BeadSort(int[] arr) {
        int n = arr.Length;
        int max = 0;

        foreach (int num in arr)
            if (num > max)
                max = num;

        int[,] beads = new int[n, max];

        for (int i = 0; i < n; i++)
            for (int j = 0; j < arr[i]; j++)
                beads[i, j] = 1;

        for (int j = 0; j < max; j++) {
            int count = 0;

            for (int i = 0; i < n; i++)
                count += beads[i, j];

            for (int i = 0; i < n; i++)
                beads[i, j] = (i >= n - count) ? 1 : 0;
        }

        for (int i = 0; i < n; i++) {
            int val = 0;
            for (int j = 0; j < max; j++)
                val += beads[i, j];
            arr[i] = val;
        }
    }

    static void Main() {
        Console.Write("Enter non-negative integers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        BeadSort(arr);

        Console.Write("Sorted array: ");
        foreach (int x in arr) Console.Write(x + " ");
    }
}
      

<?php

function beadSort(&$arr) {
    foreach ($arr as $num)
        if ($num < 0)
            die("Bead Sort requires non-negative integers.\n");

    $n = count($arr);
    $max = max($arr);

    $beads = array_fill(0, $n, array_fill(0, $max, 0));

    for ($i = 0; $i < $n; $i++)
        for ($j = 0; $j < $arr[$i]; $j++)
            $beads[$i][$j] = 1;

    for ($j = 0; $j < $max; $j++) {
        $count = 0;

        for ($i = 0; $i < $n; $i++)
            $count += $beads[$i][$j];

        for ($i = 0; $i < $n; $i++)
            $beads[$i][$j] = ($i >= $n - $count) ? 1 : 0;
    }

    for ($i = 0; $i < $n; $i++)
        $arr[$i] = array_sum($beads[$i]);
}

$arr = array_map('intval', explode(" ", readline("Enter non-negative integers: ")));
beadSort($arr);
echo "Sorted array: " . implode(" ", $arr);

?>
1