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
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