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));
}
}