PHP Array Exercises : Sort an array of positive integers using the Bead-Sort Algorithm
Write a PHP program to sort an array of positive integers using the Bead-Sort Algorithm.
According to Wikipedia "Bead-sort is a natural sorting algorithm, developed by Joshua J. Arulanandham, Cristian S. Calude and Michael J. Dinneen in 2002. Both digital and analog hardware implementations of bead sort can achieve a sorting time of O(n); however, the implementation of this algorithm tends to be significantly slower in software and can only be used to sort lists of positive integers".
Input array : Array ( [0] => 5 [1] => 3 [2] => 1 [3] => 3 [4] => 8 [5] => 7 [6] => 4 [7] => 1 [8] => 1 [9] => 3 )
Sample Solution:
<?php
// Define a function named 'columns' that transposes a 2D array
function columns($uarr)
{
$n = $uarr;
// Check if the array is empty
if (count($n) == 0)
return array();
// Check if the array has only one element
else if (count($n) == 1)
return array_chunk($n[0], 1);
// Add a NULL element to the beginning of the array
array_unshift($uarr, NULL);
// Use 'array_map' to transpose the 2D array
$transpose = call_user_func_array('array_map', $uarr);
// Use 'array_map' to filter out NULL values from each column
return array_map('array_filter', $transpose);
}
// Define a function named 'bead_sort' that performs bead sort on an array
function bead_sort($uarr)
{
// Create an array of poles based on the values in the input array
foreach ($uarr as $e)
$poles [] = array_fill(0, $e, 1);
// Use 'array_map' to count the beads in each column of the transposed array
return array_map('count', columns(columns($poles)));
}
// Output a message indicating the original array
echo 'Original Array : ' . '';
// Display the original array
print_r(array(5, 3, 1, 3, 8, 7, 4, 1, 1, 3));
// Output a newline character for better formatting
echo '
'.'After Bead sort : ' . '';
// Display the array after applying bead sort
print_r(bead_sort(array(5, 3, 1, 3, 8, 7, 4, 1, 1, 3)));
?>
Output:
Original Array :
Array
(
[0] => 5
[1] => 3
[2] => 1
[3] => 3
[4] => 8
[5] => 7
[6] => 4
[7] => 1
[8] => 1
[9] => 3
)
After Bead sort :
Array
(
[0] => 8
[1] => 7
[2] => 5
[3] => 4
[4] => 3
[5] => 3
[6] => 3
[7] => 1
[8] => 1
[9] => 1
)
Flowchart:
PHP Code Editor:
Contribute your code and comments through Disqus.
Previous: Write a PHP script to calculate and display average temperature, five lowest and highest temperatures.
Next: Write a PHP program to merge (by index) the specified two arrays.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.