# What is Bead Sort

**Bead sort**is a sorting algorithm that works by moving beads around on a series of rods. Each bead represents a number, and the algorithm sorts the numbers by moving the beads up and down until they settle into their correct positions.

Here's how it works:

1. Start with an unsorted list of numbers.

2. Create a series of rods, one for each number in the list.

3. Put the beads (or balls) on top of the rods. Each bead represents a number.

4. Let the beads fall down the rods until they hit a surface. The beads will stack up on top of each other, and the height of each stack will represent the size of the corresponding number.

5. Move the beads back up the rods until they reach the top.

6. Repeat this process until the beads have settled into their correct positions.

7. Read off the sorted list from the bottom of the rods, starting with the shortest stack and ending with the tallest.

Bead sort is a relatively simple algorithm that can sort numbers quickly, but it can be less efficient than other sorting algorithms for very large lists of numbers.

## Who invented it?

The exact origin of bead sort is unclear, and there isn't a single person or organization that can be credited with inventing it.

However, it is believed that the algorithm was developed independently by several people in different parts of the world. One early reference to bead sort can be found in a 2002 paper by Joshua J. Arulanandham and Colin S. Gordon, where they describe a variation of the algorithm that they call "Gravity Sort."

Since then, bead sort has been studied and implemented by various researchers and computer scientists as a simple sorting algorithm with interesting properties.

However, it is believed that the algorithm was developed independently by several people in different parts of the world. One early reference to bead sort can be found in a 2002 paper by Joshua J. Arulanandham and Colin S. Gordon, where they describe a variation of the algorithm that they call "Gravity Sort."

Since then, bead sort has been studied and implemented by various researchers and computer scientists as a simple sorting algorithm with interesting properties.

## Pseudocode

```
function beadSort(arr):
// Count the maximum value in the array
maxVal = arr[0]
for i = 1 to arr.length - 1:
if arr[i] > maxVal:
maxVal = arr[i]
// Create a matrix of beads with dimensions (maxVal, len(arr))
beads = matrix(maxVal, arr.length)
// Place beads on the rods
for i = 0 to arr.length - 1:
for j = 0 to arr[i] - 1:
beads[j][i] = 1
// Let the beads fall
for i = 0 to maxVal - 1:
// Count the number of beads in each rod
sum = 0
for j = 0 to arr.length - 1:
if beads[i][j] == 1:
sum += 1
// Move the beads back up the rods
for j = 0 to arr.length - 1:
if sum > 0:
beads[i][j] = 1
sum -= 1
else:
beads[i][j] = 0
// Read off the sorted array from the matrix
sortedArr = []
for i = 0 to arr.length - 1:
sum = 0
for j = 0 to maxVal - 1:
if beads[j][i] == 1:
sum += 1
sortedArr.append(sum)
return sortedArr
```

- First, the maximum value in the input array is determined.
- Then, a matrix of beads is created with dimensions (maxVal, len(arr)), where each bead represents a number in the input array.
- The beads are placed on the rods by iterating through the input array and placing beads on each rod up to the height of the corresponding number.
- The beads are allowed to fall by counting the number of beads in each column and moving them back up the rods until they reach their correct position.
- Finally, the sorted array is read off from the matrix and returned.
- Overall, bead sort is a relatively simple algorithm that works by simulating the physical process of gravity on a series of beads.

## Sample Code

```
// C++ code snippet
vector
``` beadSort(vector arr) {
// Count the maximum value in the array
int maxVal = arr[0];
for (int i = 1; i < arr.size(); i++) {
if (arr[i] > maxVal) {
maxVal = arr[i];
}
}
// Create a matrix of beads with dimensions (maxVal, arr.size())
vector> beads(maxVal, vector(arr.size()));
// Place beads on the rods
for (int i = 0; i < arr.size(); i++) {
for (int j = 0; j < arr[i]; j++) {
beads[j][i] = 1;
}
}
// Let the beads fall
for (int i = 0; i < maxVal; i++) {
// Count the number of beads in each rod
int sum = 0;
for (int j = 0; j < arr.size(); j++) {
if (beads[i][j] == 1) {
sum += 1;
}
}
// Move the beads back up the rods
for (int j = 0; j < arr.size(); j++) {
if (sum > 0) {
beads[i][j] = 1;
sum -= 1;
}
else {
beads[i][j] = 0;
}
}
}
// Read off the sorted array from the matrix
vector sortedArr(arr.size());
for (int i = 0; i < arr.size(); i++) {
int sum = 0;
for (int j = 0; j < maxVal; j++) {
if (beads[j][i] == 1) {
sum += 1;
}
}
sortedArr[i] = sum;
}
return sortedArr;
}
int main() {
vector arr = {5, 3, 1, 4, 2};
vector sortedArr = beadSort(arr);
for (int i = 0; i < sortedArr.size(); i++) {
cout << sortedArr[i] << " ";
}
cout << endl;
return 0;
}

```
# Python code snippet
def bead_sort(arr):
# Count the maximum value in the array
max_val = max(arr)
# Create a matrix of beads with dimensions (max_val, len(arr))
beads = [[0] * len(arr) for _ in range(max_val)]
# Place beads on the rods
for i, num in enumerate(arr):
for j in range(num):
beads[j][i] = 1
# Let the beads fall
for i in range(max_val):
# Count the number of beads in each rod
sum = 0
for j in range(len(arr)):
if beads[i][j] == 1:
sum += 1
# Move the beads back up the rods
for j in range(len(arr)):
if sum > 0:
beads[i][j] = 1
sum -= 1
else:
beads[i][j] = 0
# Read off the sorted array from the matrix
sorted_arr = [0] * len(arr)
for i in range(len(arr)):
sum = 0
for j in range(max_val):
if beads[j][i] == 1:
sum += 1
sorted_arr[i] = sum
return sorted_arr
```

```
import java.util.Arrays;
public class BeadSort {
public static int[] beadSort(int[] arr) {
// Count the maximum value in the array
int maxVal = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > maxVal) {
maxVal = arr[i];
}
}
// Create a matrix of beads with dimensions (maxVal, arr.length)
int[][] beads = new int[maxVal][arr.length];
// Place beads on the rods
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i]; j++) {
beads[j][i] = 1;
}
}
// Let the beads fall
for (int i = 0; i < maxVal; i++) {
// Count the number of beads in each rod
int sum = 0;
for (int j = 0; j < arr.length; j++) {
if (beads[i][j] == 1) {
sum += 1;
}
}
// Move the beads back up the rods
for (int j = 0; j < arr.length; j++) {
if (sum > 0) {
beads[i][j] = 1;
sum -= 1;
}
else {
beads[i][j] = 0;
}
}
}
// Read off the sorted array from the matrix
int[] sortedArr = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
int sum = 0;
for (int j = 0; j < maxVal; j++) {
if (beads[j][i] == 1) {
sum += 1;
}
}
sortedArr[i] = sum;
}
return sortedArr;
}
public static void main(String[] args) {
int[] arr = {5, 3, 1, 4, 2};
int[] sortedArr = beadSort(arr);
System.out.println(Arrays.toString(sortedArr));
}
}
```

## Time and Space Complexity

The time complexity of bead sort is O(n * max_val), where n is the length of the input array and max_val is the maximum value in the input array. This is because the algorithm iterates over each element of the input array to place the beads on the rods, and then iterates over each rod to let the beads fall and move them back up the rods. The size of the matrix of beads is (max_val, n), so the total number of iterations is O(n * max_val).

The space complexity of bead sort is also O(n * max_val), since we need to create a matrix of beads with dimensions (max_val, n) to hold the beads. In the worst case where all the elements of the input array are the same, the matrix will contain n * max_val beads.

The space complexity of bead sort is also O(n * max_val), since we need to create a matrix of beads with dimensions (max_val, n) to hold the beads. In the worst case where all the elements of the input array are the same, the matrix will contain n * max_val beads.

## Advantages

- Advantages of bead sort:
- Bead sort is a simple and easy-to-implement algorithm that requires no comparison operations.
- It can be used to sort arrays with non-integer values, by scaling the values appropriately.
- Bead sort is a stable sorting algorithm, meaning that it preserves the relative order of equal elements in the sorted array.

## Disadvantages

- Bead sort has a time complexity of O(n * max_val), where n is the length of the input array and max_val is the maximum value in the input array. This makes it less efficient than many other sorting algorithms, especially for large values of max_val.
- Bead sort requires a matrix of beads to hold the elements, which can be memory-intensive for large input arrays or large values of max_val.
- Bead sort is not an in-place sorting algorithm, meaning that it requires additional memory to store the matrix of beads. This can be a disadvantage in applications with limited memory resources.