Algorithm Speed (2.00) :

Array Size (100) :

Bead Sort :

Author(s) : Joshua J. Arulanandham, Cristian S. Calude and Michael J. Dinneen Date : 2002

Bead sort, also known as counting sort with linked lists, is a less common sorting technique that utilizes physical beads with unique colors to represent the data. It relies on the ability to physically manipulate the beads based on their colors. While conceptually interesting, bead sort is a theoretical algorithm not typically used in practical sorting tasks.

Time Complexity	O(S)
Best Case	O(n)
Worst Case	O(S)
Space Complexity	O(n²)
Stable	Unknown

def bead_sort(numbers):
	rows = max(numbers) + 1
	cols = len(numbers)
	beads = [[0 for _ in range(cols)] for _ in range(rows)]
	for num in numbers:
		beads[num][numbers.index(num)] = 1
	for col in range(cols):
		for row in range(rows - 2, -1, -1):
			if beads[row][col] == 1:
				beads[row][col] = 0
				beads[row + 1][col] = 1
	sorted_numbers = []
	for col in range(cols):
		if beads[0][col] == 1:
			sorted_numbers.append(col)
	return sorted_numbers

# Example usage
numbers = [3, 1, 4, 1, 5, 9, 2, 6]
print("Original numbers:", numbers)
sorted_numbers = bead_sort(numbers.copy())  # Avoid modifying the original list
print("Sorted numbers:", sorted_numbers)

function beadSort(numbers) {
	const rows = Math.max(...numbers) + 1;
	const cols = numbers.length;
	const beads = Array.from({ length: rows }, () => Array(cols).fill(0));
		numbers.forEach((num, index) => beads[num][index] = 1);
	for (let col = 0; col < cols; col++) {
		for (let row = rows - 2; row >= 0; row--) {
			if (beads[row][col] === 1) {
				beads[row][col] = 0;
				beads[row + 1][col] = 1;
			}
		}
	}
	const sortedNumbers = [];
	for (let col = 0; col < cols; col++) {
		if (beads[0][col] === 1) {
			sortedNumbers.push(col);
		}
	}
	return sortedNumbers;
}

// Example usage
const numbers = [3, 1, 4, 1, 5, 9, 2, 6];
console.log("Original numbers:", numbers);
const sortedNumbers = beadSort([...numbers]);  // Spread operator to avoid modifying the original array
console.log("Sorted numbers:", sortedNumbers);

public class BeadSort { public static int[] beadSort(int[] numbers) {
	int rows = Arrays.stream(numbers).max().getAsInt() + 1; 
	int cols = numbers.length; 
		int[][] beads = new int[rows][cols]; 
	for (int i = 0; i < numbers.length; i++) { 
		beads[numbers[i]][i] = 1; 
	} 
	for (int col = 0; col < cols; col++) { 
		for (int row = rows - 2; row >= 0; row--) { 
			if (beads[row][col] == 1) { 
				beads[row][col] = 0; 
				beads[row + 1][col] = 1; 
			}
		}
	} 
		int[] sortedNumbers = new int[cols]; 
		int index = 0; 
	for (int col = 0; col < cols; col++) { 
		if (beads[0][col] == 1) { 
			sortedNumbers[index++] = col; 
		}
	}
	return sortedNumbers; 
} } 

// Example usage 
int[] numbers = {3, 1, 4, 1, 5, 9, 2, 6}; 
System.out.println("Original numbers: " + Arrays.toString(numbers)); 
int[] sortedNumbers = beadSort(numbers.clone());  // Clone to avoid modifying the original array 
System.out.println("Sorted numbers: " + Arrays.toString(sortedNumbers));

package main

import (
	"fmt"
)

func beadSort(numbers []int) []int {
	
	rows := max(numbers) + 1
	cols := len(numbers)
	beads := make([][]int, rows)
	for i := range beads {
		beads[i] = make([]int, cols)
	}
	for i, num := range numbers {
		beads[num][i] = 1
	}
	for col := range numbers {
		for row := rows - 2; row >= 0; row-- {
			if beads[row][col] == 1 {
				beads[row][col] = 0
				beads[row+1][col] = 1
			}
		}
	}
	sortedNumbers := make([]int, 0, cols)
	for col := range numbers {
		if beads[0][col] == 1 {
			sortedNumbers = append(sortedNumbers, col)
		}
	}
	return sortedNumbers
}

func max(arr []int) int {
	maxVal := arr[0]
	for _, val := range arr {
		if val > maxVal {
			maxVal = val
		}
	}
	return maxVal
} 

func main() {
	numbers := []int{3, 1, 4, 1, 5, 9, 2, 6}
	fmt.Println("Original numbers:", numbers)
	sortedNumbers := beadSort(numbers)
	fmt.Println("Sorted numbers:", sortedNumbers)
}

#include <stdio.h>
#include <stdlib.h>

int *beadSort(int *numbers, int n) {
	int rows = *numbers + 1;
	int cols = n;
		int **beads = malloc(rows * sizeof(int*));
	for (int i = 0; i < rows; i++) {
		beads[i] = malloc(cols * sizeof(int));
		for (int j = 0; j < cols; j++) {
			beads[i][j] = 0;  // Initialize all beads to empty (0)
		}
	}
	for (int i = 0; i < n; i++) {
		beads[numbers[i]][i] = 1;
	}
	for (int col = 0; col < n; col++) {
		for (int row = rows - 2; row >= 0; row--) {
			if (beads[row][col] == 1) {
				beads[row][col] = 0;
				beads[row + 1][col] = 1;
			}
		}
	}
		int *sortedNumbers = malloc(n * sizeof(int));
		int index = 0;
	for (int col = 0; col < n; col++) {
		if (beads[0][col] == 1) {
			sortedNumbers[index++] = col;
		}
	}
	for (int i = 0; i < rows; i++) {
		free(beads[i]);
	}
	free(beads);
	return sortedNumbers;
}

int main() {
	int numbers[] = {3, 1, 4, 1, 5, 9, 2, 6};
	int n = sizeof(numbers) / sizeof(numbers[0]);
	printf("Original numbers: ");
	for (int i = 0; i < n; i++) {
		printf("%d ", numbers[i]);
	}
	printf("\n");
	int *sortedNumbers = beadSort(numbers, n);
	printf("Sorted numbers: ");
	for (int i = 0; i < n; i++) {
		printf("%d ", sortedNumbers[i]);
	}
	printf("\n");
	free(sortedNumbers);  // Free memory allocated for sorted numbers
	return 0;
}