Skip to main content

Bead Sort

Bead Sort is a simple and efficient sorting algorithm that works by sliding beads along a rod. It is also known as the gravity sort, or the bin sort.

The algorithm operates on a collection of input values that are represented by beads on a set of vertical rods. Each rod corresponds to a digit in the input values. The beads are then allowed to slide down the rods under the influence of gravity until they come to rest in a tray at the bottom of the rods.

The beads are sorted based on their position in the tray, which corresponds to the sorted order of the input values. The algorithm works by repeatedly passing the beads along the rods, with each pass sorting the beads based on the previous pass.

The time complexity of the algorithm is O(nw), where n is the number of input values, and w is the word size. The algorithm is particularly efficient when the number of distinct input values is small, making it useful for sorting integers in a limited range.

Although the algorithm is simple and efficient, it is not commonly used in practice because it requires physical manipulation of objects and is not easily adaptable to digital computing.

Here given code implementation process.

// C Program
// Bead Sort
#include <stdio.h>

//Display elements of given sequence
void display(int sequence[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		printf("  %d", sequence[i]);
	}
	printf("\n");
}
//Get the max element of given sequence in unordered elements
int max_element(int sequence[], int size)
{
	int max = sequence[0];
	for (int i = 1; i < size; ++i)
	{
		if (max < sequence[i])
		{
			max = sequence[i];
		}
	}
	return max;
}
//Check that whether given sequence contains positive elements or not
int is_negative(int sequence[], int size)
{
	for (int i = 1; i < size; ++i)
	{
		if (sequence[i] < 0)
		{
			return 1;
		}
	}
	return 0;
}
/*
   Implemented bead sort 
*/
void bead_sort(int sequence[], int size)
{
	if (is_negative(sequence, size))
	{
		printf("\n Sequence are not valid \n");
	}
	else
	{
		// Find max element of given sequence
		int max = max_element(sequence, size);
		int auxiliary[max];
		//Define loop controlling variable
		int i = 0;
		int j = 0;
		int k = 0;
		//Set initial value
		for (i = 0; i < max; ++i)
		{
			auxiliary[i] = 0;
		}
		// Count beads
		for (i = 0; i < size; ++i)
		{
			for (j = 0; j < sequence[i]; ++j)
			{
				auxiliary[j] = auxiliary[j] + 1;
			}
		}
		for (i = 0; i < size; ++i)
		{
			k = 0;
			// Count beads which is more than zero
			for (j = 0; j < max; ++j)
			{
				if (auxiliary[j] > 0)
				{
					k++;
				}
			}
			// Reduce beads which is more than zero  
			for (j = 0; j < max; ++j)
			{
				if (auxiliary[j] > 0)
				{
					auxiliary[j]--;
				}
			}
			// Fill calculate result into input sequence
			sequence[i] = k;
		}
	}
}
int main()
{
	// Define array of positive integer elements
	int s1[] = {
		6 , 2 , 8 , 5 , 2 , 4 , 1 , 17 , 21 , 12 , 1 , 14 , 9 , 3 , 5 , 7 , 2 , 9
	};
	int s2[] = {
		7 , 2 , 0 , 9 , 1 , 0 , 3 , 6 , 2 , 7 , 3 , 1
	};
	// Test case A
	int size = sizeof(s1) / sizeof(s1[0]);
	printf(" Array \n");
	display(s1, size);
	printf(" Sorted descending order\n");
	bead_sort(s1, size);
	display(s1, size);
	// Test case B
	size = sizeof(s2) / sizeof(s2[0]);
	printf("\n Array \n");
	display(s2, size);
	bead_sort(s2, size);
	printf(" Sorted descending order \n");
	display(s2, size);
	return 0;
}

Output

 Array
  6  2  8  5  2  4  1  17  21  12  1  14  9  3  5  7  2  9
 Sorted descending order
  21  17  14  12  9  9  8  7  6  5  5  4  3  2  2  2  1  1

 Array
  7  2  0  9  1  0  3  6  2  7  3  1
 Sorted descending order
  9  7  7  6  3  3  2  2  1  1  0  0
/*
  Java program
  Bead Sort
*/
public class Sorting
{
	// Display elements of given sequence
	public void display(int[] sequence, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			System.out.print("   " + sequence[i]);
		}
		System.out.print("\n");
	}
	//Get the max element of given sequence in unordered elements
	public int maxElement(int[] sequence, int size)
	{
		int max = sequence[0];
		for (int i = 1; i < size; ++i)
		{
			if (max < sequence[i])
			{
				max = sequence[i];
			}
		}
		return max;
	}
	//Check that whether given sequence contains positive elements or not
	public boolean isNegative(int[] sequence, int size)
	{
		for (int i = 1; i < size; ++i)
		{
			if (sequence[i] < 0)
			{
				return true;
			}
		}
		return false;
	}
	/*
	   Implemented bead sort 
	*/
	public void beadSort(int[] sequence, int size)
	{
		if (isNegative(sequence, size))
		{
			System.out.print("\n Sequence are not valid \n");
		}
		else
		{
			// Find max element of given sequence
			int max = maxElement(sequence, size);
			int[] auxiliary = new int[max];
			//Define loop controlling variable
			int i = 0;
			int j = 0;
			int k = 0;
			//Set initial value
			for (i = 0; i < max; ++i)
			{
				auxiliary[i] = 0;
			}
			// Count beads
			for (i = 0; i < size; ++i)
			{
				for (j = 0; j < sequence[i]; ++j)
				{
					auxiliary[j] = auxiliary[j] + 1;
				}
			}
			for (i = 0; i < size; ++i)
			{
				k = 0;
				// Count beads which is more than zero
				for (j = 0; j < max; ++j)
				{
					if (auxiliary[j] > 0)
					{
						k++;
					}
				}
				// Reduce beads which is more than zero  
				for (j = 0; j < max; ++j)
				{
					if (auxiliary[j] > 0)
					{
						auxiliary[j]--;
					}
				}
				// Fill calculate result into input sequence
				sequence[i] = k;
			}
		}
	}
	public static void main(String[] args)
	{
		Sorting task = new Sorting();
		// Define array of positive integer elements
		int[] s1 = {
			6 , 2 , 8 , 5 , 2 , 4 , 1 , 17 , 21 , 12 , 1 , 14 , 9 , 3 , 5 , 7 , 2 , 9
		};
		int[] s2 = {
			7 , 2 , 0 , 9 , 1 , 0 , 3 , 6 , 2 , 7 , 3 , 1
		};
		// Test case A
		int size = s1.length;
		System.out.print(" Array \n");
		task.display(s1, size);
		System.out.print(" Sorted descending order\n");
		task.beadSort(s1, size);
		task.display(s1, size);
		// Test case B
		size = s2.length;
		System.out.print("\n Array \n");
		task.display(s2, size);
		task.beadSort(s2, size);
		System.out.print(" Sorted descending order \n");
		task.display(s2, size);
	}
}

Output

 Array
   6   2   8   5   2   4   1   17   21   12   1   14   9   3   5   7   2   9
 Sorted descending order
   21   17   14   12   9   9   8   7   6   5   5   4   3   2   2   2   1   1

 Array
   7   2   0   9   1   0   3   6   2   7   3   1
 Sorted descending order
   9   7   7   6   3   3   2   2   1   1   0   0
// Include header file
#include <iostream>

using namespace std;
/*
  C++ program
  Bead Sort
*/
class Sorting
{
	public:
		// Display elements of given sequence
		void display(int sequence[], int size)
		{
			for (int i = 0; i < size; ++i)
			{
				cout << "   " << sequence[i];
			}
			cout << "\n";
		}
	//Get the max element of given sequence in unordered elements
	int maxElement(int sequence[], int size)
	{
		int max = sequence[0];
		for (int i = 1; i < size; ++i)
		{
			if (max < sequence[i])
			{
				max = sequence[i];
			}
		}
		return max;
	}
	//Check that whether given sequence contains positive elements or not
	bool isNegative(int sequence[], int size)
	{
		for (int i = 1; i < size; ++i)
		{
			if (sequence[i] < 0)
			{
				return true;
			}
		}
		return false;
	}
	/*
		   Implemented bead sort 
		*/
	void beadSort(int sequence[], int size)
	{
		if (this->isNegative(sequence, size))
		{
			cout << "\n Sequence are not valid \n";
		}
		else
		{
			// Find max element of given sequence
			int max = this->maxElement(sequence, size);
			int auxiliary[max];
			//Define loop controlling variable
			int i = 0;
			int j = 0;
			int k = 0;
			//Set initial value
			for (i = 0; i < max; ++i)
			{
				auxiliary[i] = 0;
			}
			// Count beads
			for (i = 0; i < size; ++i)
			{
				for (j = 0; j < sequence[i]; ++j)
				{
					auxiliary[j] = auxiliary[j] + 1;
				}
			}
			for (i = 0; i < size; ++i)
			{
				k = 0;
				// Count beads which is more than zero
				for (j = 0; j < max; ++j)
				{
					if (auxiliary[j] > 0)
					{
						k++;
					}
				}
				// Reduce beads which is more than zero
				for (j = 0; j < max; ++j)
				{
					if (auxiliary[j] > 0)
					{
						auxiliary[j]--;
					}
				}
				// Fill calculate result into input sequence
				sequence[i] = k;
			}
		}
	}
};
int main()
{
	Sorting task = Sorting();
	// Define array of positive integer elements
	int s1[] = {
		6 , 2 , 8 , 5 , 2 , 4 , 1 , 17 , 21 , 12 , 1 , 14 , 9 , 3 , 5 , 7 , 2 , 9
	};
	int s2[] = {
		7 , 2 , 0 , 9 , 1 , 0 , 3 , 6 , 2 , 7 , 3 , 1
	};
	// Test case A
	int size = sizeof(s1) / sizeof(s1[0]);
	cout << " Array \n";
	task.display(s1, size);
	cout << " Sorted descending order\n";
	task.beadSort(s1, size);
	task.display(s1, size);
	// Test case B
	size = sizeof(s2) / sizeof(s2[0]);
	cout << "\n Array \n";
	task.display(s2, size);
	task.beadSort(s2, size);
	cout << " Sorted descending order \n";
	task.display(s2, size);
	return 0;
}

Output

 Array
   6   2   8   5   2   4   1   17   21   12   1   14   9   3   5   7   2   9
 Sorted descending order
   21   17   14   12   9   9   8   7   6   5   5   4   3   2   2   2   1   1

 Array
   7   2   0   9   1   0   3   6   2   7   3   1
 Sorted descending order
   9   7   7   6   3   3   2   2   1   1   0   0
// Include namespace system
using System;
/*
  C# program
  Bead Sort
*/
public class Sorting
{
	// Display elements of given sequence
	public void display(int[] sequence, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			Console.Write("   " + sequence[i]);
		}
		Console.Write("\n");
	}
	//Get the max element of given sequence in unordered elements
	public int maxElement(int[] sequence, int size)
	{
		int max = sequence[0];
		for (int i = 1; i < size; ++i)
		{
			if (max < sequence[i])
			{
				max = sequence[i];
			}
		}
		return max;
	}
	//Check that whether given sequence contains positive elements or not
	public Boolean isNegative(int[] sequence, int size)
	{
		for (int i = 1; i < size; ++i)
		{
			if (sequence[i] < 0)
			{
				return true;
			}
		}
		return false;
	}
	/*
		   Implemented bead sort 
		*/
	public void beadSort(int[] sequence, int size)
	{
		if (isNegative(sequence, size))
		{
			Console.Write("\n Sequence are not valid \n");
		}
		else
		{
			// Find max element of given sequence
			int max = maxElement(sequence, size);
			int[] auxiliary = new int[max];
			//Define loop controlling variable
			int i = 0;
			int j = 0;
			int k = 0;
			//Set initial value
			for (i = 0; i < max; ++i)
			{
				auxiliary[i] = 0;
			}
			// Count beads
			for (i = 0; i < size; ++i)
			{
				for (j = 0; j < sequence[i]; ++j)
				{
					auxiliary[j] = auxiliary[j] + 1;
				}
			}
			for (i = 0; i < size; ++i)
			{
				k = 0;
				// Count beads which is more than zero
				for (j = 0; j < max; ++j)
				{
					if (auxiliary[j] > 0)
					{
						k++;
					}
				}
				// Reduce beads which is more than zero
				for (j = 0; j < max; ++j)
				{
					if (auxiliary[j] > 0)
					{
						auxiliary[j]--;
					}
				}
				// Fill calculate result into input sequence
				sequence[i] = k;
			}
		}
	}
	public static void Main(String[] args)
	{
		Sorting task = new Sorting();
		// Define array of positive integer elements
		int[] s1 = {
			6 , 2 , 8 , 5 , 2 , 4 , 1 , 17 , 21 , 12 , 1 , 14 , 9 , 3 , 5 , 7 , 2 , 9
		};
		int[] s2 = {
			7 , 2 , 0 , 9 , 1 , 0 , 3 , 6 , 2 , 7 , 3 , 1
		};
		// Test case A
		int size = s1.Length;
		Console.Write(" Array \n");
		task.display(s1, size);
		Console.Write(" Sorted descending order\n");
		task.beadSort(s1, size);
		task.display(s1, size);
		// Test case B
		size = s2.Length;
		Console.Write("\n Array \n");
		task.display(s2, size);
		task.beadSort(s2, size);
		Console.Write(" Sorted descending order \n");
		task.display(s2, size);
	}
}

Output

 Array
   6   2   8   5   2   4   1   17   21   12   1   14   9   3   5   7   2   9
 Sorted descending order
   21   17   14   12   9   9   8   7   6   5   5   4   3   2   2   2   1   1

 Array
   7   2   0   9   1   0   3   6   2   7   3   1
 Sorted descending order
   9   7   7   6   3   3   2   2   1   1   0   0
<?php
/*
  Php program
  Bead Sort
*/
class Sorting
{
	// Display elements of given sequence
	public	function display( & $sequence, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			echo "   ". $sequence[$i];
		}
		echo "\n";
	}
	//Get the max element of given sequence in unordered elements
	public	function maxElement( & $sequence, $size)
	{
		$max = $sequence[0];
		for ($i = 1; $i < $size; ++$i)
		{
			if ($max < $sequence[$i])
			{
				$max = $sequence[$i];
			}
		}
		return $max;
	}
	//Check that whether given sequence contains positive elements or not
	public	function isNegative( & $sequence, $size)
	{
		for ($i = 1; $i < $size; ++$i)
		{
			if ($sequence[$i] < 0)
			{
				return true;
			}
		}
		return false;
	}
	/*
		   Implemented bead sort 
		*/
	public	function beadSort( & $sequence, $size)
	{
		if ($this->isNegative($sequence, $size))
		{
			echo "\n Sequence are not valid \n";
		}
		else
		{
			// Find max element of given sequence
			$max = $this->maxElement($sequence, $size);
			$auxiliary = array_fill(0, $max, 0);
			//Define loop controlling variable
			$i = 0;
			$j = 0;
			$k = 0;
			//Set initial value
			for ($i = 0; $i < $max; ++$i)
			{
				$auxiliary[$i] = 0;
			}
			// Count beads
			for ($i = 0; $i < $size; ++$i)
			{
				for ($j = 0; $j < $sequence[$i]; ++$j)
				{
					$auxiliary[$j] = $auxiliary[$j] + 1;
				}
			}
			for ($i = 0; $i < $size; ++$i)
			{
				$k = 0;
				// Count beads which is more than zero
				for ($j = 0; $j < $max; ++$j)
				{
					if ($auxiliary[$j] > 0)
					{
						$k++;
					}
				}
				// Reduce beads which is more than zero
				for ($j = 0; $j < $max; ++$j)
				{
					if ($auxiliary[$j] > 0)
					{
						$auxiliary[$j]--;
					}
				}
				// Fill calculate result into input sequence
				$sequence[$i] = $k;
			}
		}
	}
}

function main()
{
	$task = new Sorting();
	// Define array of positive integer elements
	$s1 = array(6, 2, 8, 5, 2, 4, 1, 17, 21, 12, 1, 14, 9, 3, 5, 7, 2, 9);
	$s2 = array(7, 2, 0, 9, 1, 0, 3, 6, 2, 7, 3, 1);
	// Test case A
	$size = count($s1);
	echo " Array \n";
	$task->display($s1, $size);
	echo " Sorted descending order\n";
	$task->beadSort($s1, $size);
	$task->display($s1, $size);
	// Test case B
	$size = count($s2);
	echo "\n Array \n";
	$task->display($s2, $size);
	$task->beadSort($s2, $size);
	echo " Sorted descending order \n";
	$task->display($s2, $size);
}
main();

Output

 Array
   6   2   8   5   2   4   1   17   21   12   1   14   9   3   5   7   2   9
 Sorted descending order
   21   17   14   12   9   9   8   7   6   5   5   4   3   2   2   2   1   1

 Array
   7   2   0   9   1   0   3   6   2   7   3   1
 Sorted descending order
   9   7   7   6   3   3   2   2   1   1   0   0
/*
  Node Js program
  Bead Sort
*/
class Sorting
{
	// Display elements of given sequence
	display(sequence, size)
	{
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write("   " + sequence[i]);
		}
		process.stdout.write("\n");
	}
	//Get the max element of given sequence in unordered elements
	maxElement(sequence, size)
	{
		var max = sequence[0];
		for (var i = 1; i < size; ++i)
		{
			if (max < sequence[i])
			{
				max = sequence[i];
			}
		}
		return max;
	}
	//Check that whether given sequence contains positive elements or not
	isNegative(sequence, size)
	{
		for (var i = 1; i < size; ++i)
		{
			if (sequence[i] < 0)
			{
				return true;
			}
		}
		return false;
	}
	/*
		   Implemented bead sort 
		*/
	beadSort(sequence, size)
	{
		if (this.isNegative(sequence, size))
		{
			process.stdout.write("\n Sequence are not valid \n");
		}
		else
		{
			// Find max element of given sequence
			var max = this.maxElement(sequence, size);
			var auxiliary = Array(max).fill(0);
			//Define loop controlling variable
			var i = 0;
			var j = 0;
			var k = 0;
			//Set initial value
			for (i = 0; i < max; ++i)
			{
				auxiliary[i] = 0;
			}
			// Count beads
			for (i = 0; i < size; ++i)
			{
				for (j = 0; j < sequence[i]; ++j)
				{
					auxiliary[j] = auxiliary[j] + 1;
				}
			}
			for (i = 0; i < size; ++i)
			{
				k = 0;
				// Count beads which is more than zero
				for (j = 0; j < max; ++j)
				{
					if (auxiliary[j] > 0)
					{
						k++;
					}
				}
				// Reduce beads which is more than zero
				for (j = 0; j < max; ++j)
				{
					if (auxiliary[j] > 0)
					{
						auxiliary[j]--;
					}
				}
				// Fill calculate result into input sequence
				sequence[i] = k;
			}
		}
	}
}

function main()
{
	var task = new Sorting();
	// Define array of positive integer elements
	var s1 = [6, 2, 8, 5, 2, 4, 1, 17, 21, 12, 1, 14, 9, 3, 5, 7, 2, 9];
	var s2 = [7, 2, 0, 9, 1, 0, 3, 6, 2, 7, 3, 1];
	// Test case A
	var size = s1.length;
	process.stdout.write(" Array \n");
	task.display(s1, size);
	process.stdout.write(" Sorted descending order\n");
	task.beadSort(s1, size);
	task.display(s1, size);
	// Test case B
	size = s2.length;
	process.stdout.write("\n Array \n");
	task.display(s2, size);
	task.beadSort(s2, size);
	process.stdout.write(" Sorted descending order \n");
	task.display(s2, size);
}
main();

Output

 Array
   6   2   8   5   2   4   1   17   21   12   1   14   9   3   5   7   2   9
 Sorted descending order
   21   17   14   12   9   9   8   7   6   5   5   4   3   2   2   2   1   1

 Array
   7   2   0   9   1   0   3   6   2   7   3   1
 Sorted descending order
   9   7   7   6   3   3   2   2   1   1   0   0
#   Python 3 program
#   Bead Sort

class Sorting :
	#  Display elements of given sequence
	def display(self, sequence, size) :
		i = 0
		while (i < size) :
			print("   ", sequence[i], end = "")
			i += 1
		
		print(end = "\n")
	
	# Get the max element of given sequence in unordered elements
	def maxElement(self, sequence, size) :
		max = sequence[0]
		i = 1
		while (i < size) :
			if (max < sequence[i]) :
				max = sequence[i]
			
			i += 1
		
		return max
	
	# Check that whether given sequence contains positive elements or not
	def isNegative(self, sequence, size) :
		i = 1
		while (i < size) :
			if (sequence[i] < 0) :
				return True
			
			i += 1
		
		return False
	
	
	# Implemented bead sort 
	def beadSort(self, sequence, size) :
		if (self.isNegative(sequence, size)) :
			print("\n Sequence are not valid ")
		else :
			#  Find max element of given sequence
			max = self.maxElement(sequence, size)
			auxiliary = [0] * (max)
			# Define loop controlling variable
			i = 0
			j = 0
			k = 0
			# Set initial value
			while (i < max) :
				auxiliary[i] = 0
				i += 1
			
			#  Count beads
			i = 0
			while (i < size) :
				j = 0
				while (j < sequence[i]) :
					auxiliary[j] = auxiliary[j] + 1
					j += 1
				
				i += 1
			
			i = 0
			while (i < size) :
				k = 0
				#  Count beads which is more than zero
				j = 0
				while (j < max) :
					if (auxiliary[j] > 0) :
						k += 1
					
					j += 1
				
				#  Reduce beads which is more than zero
				j = 0
				while (j < max) :
					if (auxiliary[j] > 0) :
						auxiliary[j] -= 1
					
					j += 1
				
				#  Fill calculate result into input sequence
				sequence[i] = k
				i += 1
			
		
	

def main() :
	task = Sorting()
	#  Define array of positive integer elements
	s1 = [6, 2, 8, 5, 2, 4, 1, 17, 21, 12, 1, 14, 9, 3, 5, 7, 2, 9]
	s2 = [7, 2, 0, 9, 1, 0, 3, 6, 2, 7, 3, 1]
	#  Test case A
	size = len(s1)
	print(" Array ")
	task.display(s1, size)
	print(" Sorted descending order")
	task.beadSort(s1, size)
	task.display(s1, size)
	#  Test case B
	size = len(s2)
	print("\n Array ")
	task.display(s2, size)
	task.beadSort(s2, size)
	print(" Sorted descending order ")
	task.display(s2, size)

if __name__ == "__main__": main()

Output

 Array
    6    2    8    5    2    4    1    17    21    12    1    14    9    3    5    7    2    9
 Sorted descending order
    21    17    14    12    9    9    8    7    6    5    5    4    3    2    2    2    1    1

 Array
    7    2    0    9    1    0    3    6    2    7    3    1
 Sorted descending order
    9    7    7    6    3    3    2    2    1    1    0    0
# Ruby program
# Bead Sort

class Sorting 
	#  Display elements of given sequence
	def display(sequence, size) 
		i = 0
		while (i < size) 
			print("   ", sequence[i])
			i += 1
		end

		print("\n")
	end

	# Get the max element of given sequence in unordered elements
	def maxElement(sequence, size) 
		max = sequence[0]
		i = 1
		while (i < size) 
			if (max < sequence[i]) 
				max = sequence[i]
			end

			i += 1
		end

		return max
	end

	# Check that whether given sequence contains positive elements or not
	def isNegative(sequence, size) 
		i = 1
		while (i < size) 
			if (sequence[i] < 0) 
				return true
			end

			i += 1
		end

		return false
	end

	# 
	# 	   Implemented bead sort 
	# 	
	
	def beadSort(sequence, size) 
		if (self.isNegative(sequence, size)) 
			print("\n Sequence are not valid \n")
		else 
			#  Find max element of given sequence
			max = self.maxElement(sequence, size)
			auxiliary = Array.new(max) {0}
			# Define loop controlling variable
			i = 0
			j = 0
			k = 0
			# Set initial value
			while (i < max) 
				auxiliary[i] = 0
				i += 1
			end

			#  Count beads
			i = 0
			while (i < size) 
				j = 0
				while (j < sequence[i]) 
					auxiliary[j] = auxiliary[j] + 1
					j += 1
				end

				i += 1
			end

			i = 0
			while (i < size) 
				k = 0
				#  Count beads which is more than zero
				j = 0
				while (j < max) 
					if (auxiliary[j] > 0) 
						k += 1
					end

					j += 1
				end

				#  Reduce beads which is more than zero
				j = 0
				while (j < max) 
					if (auxiliary[j] > 0) 
						auxiliary[j] -= 1
					end

					j += 1
				end

				#  Fill calculate result into input sequence
				sequence[i] = k
				i += 1
			end

		end

	end

end

def main() 
	task = Sorting.new()
	#  Define array of positive integer elements
	s1 = [6, 2, 8, 5, 2, 4, 1, 17, 21, 12, 1, 14, 9, 3, 5, 7, 2, 9]
	s2 = [7, 2, 0, 9, 1, 0, 3, 6, 2, 7, 3, 1]
	#  Test case A
	size = s1.length
	print(" Array \n")
	task.display(s1, size)
	print(" Sorted descending order\n")
	task.beadSort(s1, size)
	task.display(s1, size)
	#  Test case B
	size = s2.length
	print("\n Array \n")
	task.display(s2, size)
	task.beadSort(s2, size)
	print(" Sorted descending order \n")
	task.display(s2, size)
end

main()

Output

 Array 
   6   2   8   5   2   4   1   17   21   12   1   14   9   3   5   7   2   9
 Sorted descending order
   21   17   14   12   9   9   8   7   6   5   5   4   3   2   2   2   1   1

 Array 
   7   2   0   9   1   0   3   6   2   7   3   1
 Sorted descending order 
   9   7   7   6   3   3   2   2   1   1   0   0

/*
  Scala program
  Bead Sort
*/
class Sorting
{
	// Display elements of given sequence
	def display(sequence: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			print("   " + sequence(i));
			i += 1;
		}
		print("\n");
	}
	//Get the max element of given sequence in unordered elements
	def maxElement(sequence: Array[Int], size: Int): Int = {
		var max: Int = sequence(0);
		var i: Int = 1;
		while (i < size)
		{
			if (max < sequence(i))
			{
				max = sequence(i);
			}
			i += 1;
		}
		return max;
	}
	//Check that whether given sequence contains positive elements or not
	def isNegative(sequence: Array[Int], size: Int): Boolean = {
		var i: Int = 1;
		while (i < size)
		{
			if (sequence(i) < 0)
			{
				return true;
			}
			i += 1;
		}
		return false;
	}
	/*
		   Implemented bead sort 
		*/
	def beadSort(sequence: Array[Int], size: Int): Unit = {
		if (this.isNegative(sequence, size))
		{
			print("\n Sequence are not valid \n");
		}
		else
		{
			// Find max element of given sequence
			var max: Int = this.maxElement(sequence, size);
			var auxiliary: Array[Int] = Array.fill[Int](max)(0);
			//Define loop controlling variable
			var i: Int = 0;
			var j: Int = 0;
			var k: Int = 0;
			//Set initial value
			while (i < max)
			{
				auxiliary(i) = 0;
				i += 1;
			}
			// Count beads
			i = 0;
			while (i < size)
			{
				j = 0;
				while (j < sequence(i))
				{
					auxiliary(j) = auxiliary(j) + 1;
					j += 1;
				}
				i += 1;
			}
			i = 0;
			while (i < size)
			{
				k = 0;
				// Count beads which is more than zero
				j = 0;
				while (j < max)
				{
					if (auxiliary(j) > 0)
					{
						k += 1;
					}
					j += 1;
				}
				// Reduce beads which is more than zero
				j = 0;
				while (j < max)
				{
					if (auxiliary(j) > 0)
					{
						auxiliary(j) -= 1;
					}
					j += 1;
				}
				// Fill calculate result into input sequence
				sequence(i) = k;
				i += 1;
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Sorting = new Sorting();
		// Define array of positive integer elements
		var s1: Array[Int] = Array(6, 2, 8, 5, 2, 4, 1, 17, 21, 12, 1, 14, 9, 3, 5, 7, 2, 9);
		var s2: Array[Int] = Array(7, 2, 0, 9, 1, 0, 3, 6, 2, 7, 3, 1);
		// Test case A
		var size: Int = s1.length;
		print(" Array \n");
		task.display(s1, size);
		print(" Sorted descending order\n");
		task.beadSort(s1, size);
		task.display(s1, size);
		// Test case B
		size = s2.length;
		print("\n Array \n");
		task.display(s2, size);
		task.beadSort(s2, size);
		print(" Sorted descending order \n");
		task.display(s2, size);
	}
}

Output

 Array
   6   2   8   5   2   4   1   17   21   12   1   14   9   3   5   7   2   9
 Sorted descending order
   21   17   14   12   9   9   8   7   6   5   5   4   3   2   2   2   1   1

 Array
   7   2   0   9   1   0   3   6   2   7   3   1
 Sorted descending order
   9   7   7   6   3   3   2   2   1   1   0   0
/*
  Swift 4 program
  Bead Sort
*/
class Sorting
{
	// Display elements of given sequence
	func display(_ sequence: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print("   ", sequence[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	//Get the max element of given sequence in unordered elements
	func maxElement(_ sequence: [Int], _ size: Int)->Int
	{
		var max: Int = sequence[0];
		var i: Int = 1;
		while (i < size)
		{
			if (max < sequence[i])
			{
				max = sequence[i];
			}
			i += 1;
		}
		return max;
	}
	//Check that whether given sequence contains positive elements or not
	func isNegative(_ sequence: [Int], _ size: Int)->Bool
	{
		var i: Int = 1;
		while (i < size)
		{
			if (sequence[i] < 0)
			{
				return true;
			}
			i += 1;
		}
		return false;
	}
	/*
		   Implemented bead sort 
		*/
	func beadSort(_ sequence: inout[Int], _ size: Int)
	{
		if (self.isNegative(sequence, size))
		{
			print("\n Sequence are not valid ");
		}
		else
		{
			// Find max element of given sequence
			let max: Int = self.maxElement(sequence, size);
			var auxiliary: [Int] = Array(repeating: 0, count: max);
			//Define loop controlling variable
			var i: Int = 0;
			var j: Int = 0;
			var k: Int = 0;
			//Set initial value
			while (i < max)
			{
				auxiliary[i] = 0;
				i += 1;
			}
			// Count beads
			i = 0;
			while (i < size)
			{
				j = 0;
				while (j < sequence[i])
				{
					auxiliary[j] = auxiliary[j] + 1;
					j += 1;
				}
				i += 1;
			}
			i = 0;
			while (i < size)
			{
				k = 0;
				// Count beads which is more than zero
				j = 0;
				while (j < max)
				{
					if (auxiliary[j] > 0)
					{
						k += 1;
					}
					j += 1;
				}
				// Reduce beads which is more than zero
				j = 0;
				while (j < max)
				{
					if (auxiliary[j] > 0)
					{
						auxiliary[j] -= 1;
					}
					j += 1;
				}
				// Fill calculate result into input sequence
				sequence[i] = k;
				i += 1;
			}
		}
	}
}
func main()
{
	let task: Sorting = Sorting();
	// Define array of positive integer elements
	var s1: [Int] = [6, 2, 8, 5, 2, 4, 1, 17, 21, 12, 1, 14, 9, 3, 5, 7, 2, 9];
	var s2: [Int] = [7, 2, 0, 9, 1, 0, 3, 6, 2, 7, 3, 1];
	// Test case A
	var size: Int = s1.count;
	print(" Array ");
	task.display(s1, size);
	print(" Sorted descending order");
	task.beadSort(&s1, size);
	task.display(s1, size);
	// Test case B
	size = s2.count;
	print("\n Array ");
	task.display(s2, size);
	task.beadSort(&s2, size);
	print(" Sorted descending order ");
	task.display(s2, size);
}
main();

Output

 Array
    6    2    8    5    2    4    1    17    21    12    1    14    9    3    5    7    2    9
 Sorted descending order
    21    17    14    12    9    9    8    7    6    5    5    4    3    2    2    2    1    1

 Array
    7    2    0    9    1    0    3    6    2    7    3    1
 Sorted descending order
    9    7    7    6    3    3    2    2    1    1    0    0
/*
  Kotlin program
  Bead Sort
*/
class Sorting
{
	// Display elements of given sequence
	fun display(sequence: Array<Int>, size: Int): Unit
	{
		var i: Int = 0;
		while (i<size)
		{
			print("   " + sequence[i]);
			i += 1;
		}
		print("\n");
	}
	//Get the max element of given sequence in unordered elements
	fun maxElement(sequence: Array<Int>, size: Int): Int
	{
		var max: Int = sequence[0];
		var i: Int = 1;
		while (i<size)
		{
			if (max<sequence[i])
			{
				max = sequence[i];
			}
			i += 1;
		}
		return max;
	}
	//Check that whether given sequence contains positive elements or not
	fun isNegative(sequence: Array<Int>, size: Int): Boolean
	{
		var i: Int = 1;
		while (i<size)
		{
			if (sequence[i]<0)
			{
				return true;
			}
			i += 1;
		}
		return false;
	}
	/*
		   Implemented bead sort 
		*/
	fun beadSort(sequence: Array<Int>, size: Int): Unit
	{
		if (this.isNegative(sequence, size))
		{
			print("\n Sequence are not valid \n");
		}
		else
		{
			// Find max element of given sequence
			var max: Int = this.maxElement(sequence, size);
			var auxiliary: Array<Int> = Array(max)
			{
				0
			};
			//Define loop controlling variable
			var i: Int = 0;
			var j: Int ;
			var k: Int ;
			//Set initial value
			while (i<max)
			{
				auxiliary[i] = 0;
				i += 1;
			}
			// Count beads
			i = 0;
			while (i<size)
			{
				j = 0;
				while (j<sequence[i])
				{
					auxiliary[j] = auxiliary[j] + 1;
					j += 1;
				}
				i += 1;
			}
			i = 0;
			while (i<size)
			{
				k = 0;
				// Count beads which is more than zero
				j = 0;
				while (j<max)
				{
					if (auxiliary[j]>0)
					{
						k += 1;
					}
					j += 1;
				}
				// Reduce beads which is more than zero
				j = 0;
				while (j<max)
				{
					if (auxiliary[j]>0)
					{
						auxiliary[j] -= 1;
					}
					j += 1;
				}
				// Fill calculate result into input sequence
				sequence[i] = k;
				i += 1;
			}
		}
	}
}
fun main(args: Array<String>): Unit
{
	var task: Sorting = Sorting();
	// Define array of positive integer elements
	var s1: Array<Int> = arrayOf(6, 2, 8, 5, 2, 4, 1, 17, 21, 12, 1, 14, 9, 3, 5, 7, 2, 9);
	var s2: Array<Int> = arrayOf(7, 2, 0, 9, 1, 0, 3, 6, 2, 7, 3, 1);
	// Test case A
	var size: Int = s1.count();
	print(" Array \n");
	task.display(s1, size);
	print(" Sorted descending order\n");
	task.beadSort(s1, size);
	task.display(s1, size);
	// Test case B
	size = s2.count();
	print("\n Array \n");
	task.display(s2, size);
	task.beadSort(s2, size);
	print(" Sorted descending order \n");
	task.display(s2, size);
}

Output

 Array
   6   2   8   5   2   4   1   17   21   12   1   14   9   3   5   7   2   9
 Sorted descending order
   21   17   14   12   9   9   8   7   6   5   5   4   3   2   2   2   1   1

 Array
   7   2   0   9   1   0   3   6   2   7   3   1
 Sorted descending order
   9   7   7   6   3   3   2   2   1   1   0   0
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment