PHP Searching and Sorting Algorithm: Bead sort

Last update on December 20 2024 10:27:54 (UTC/GMT +8 hours)

Write a PHP program to sort a list of elements using Bead sort.

Sample Solution :

PHP Code :

<?php
// Function to convert a multidimensional array into its columnar representation
function columns($my_array) {
    // Check if the input array is empty
    if (count($my_array) == 0)
        return array();
    // Check if the input array has only one row
    else if (count($my_array) == 1)
        return array_chunk($my_array[0], 1); // Split the single row into individual elements
    array_unshift($my_array, NULL); // Add a null element to the beginning of the array
    // Transpose the array using array_map and call_user_func_array
    $transpose = call_user_func_array('array_map', $my_array);
    // Filter out null elements from each column
    return array_map('array_filter', $transpose);
}

// Function to perform bead sort on an array
function bead_sort($my_array) {
    $poles = array(); // Initialize an empty array to represent the poles
    // Create poles with beads corresponding to each element in the input array
    foreach ($my_array as $e)
        $poles []= array_fill(0, $e, 1); // Fill each pole with beads
    // Convert the array of poles into its columnar representation and then back into an array
    return array_map('count', columns(columns($poles))); // Count the number of beads in each column
}

$test_array = array(3, 2, 5, 4, 1, 100); // Define an example array
echo "\nOriginal Array :\n";
echo implode(', ',$test_array ); // Print the original array
echo "\nSorted Array :\n";
echo implode(', ',bead_sort($test_array)). PHP_EOL; // Print the sorted array
?>

Output:

Original Array                                                      
:3, 2, 5, 4, 1, 100                                                 
Sorted Array :                                                      
100, 5, 4, 3, 2, 1  

Explanation:

In the exercise above,

• columns function:
• This function takes a multidimensional array as input and converts it into its columnar representation.
• It first checks if the input array is empty or has only one row. If so, it returns the array unchanged or splits the single row into individual elements, respectively.
• It then adds a null element to the beginning of the input array.
• Using "array_map()" and "call_user_func_array()", it transposes the array, effectively converting rows into columns.
• Finally, it filters out any null elements from each column using 'array_filter' and returns the resulting columnar representation.
• bead_sort function:
• This function implements the bead sort algorithm to sort an array of integers.
• It starts by initializing an empty array called '$poles' to represent the poles used in the bead sort algorithm.
• For each element '$e' in the input array '$my_array', it creates a pole with '$e' beads (represented as ones in an array).
• After creating the poles, it converts the array of poles into its columnar representation using the "columns()" function twice.
• Then, it counts the number of beads in each column using array_map('count', ...), effectively sorting the array.
• The sorted counts are then returned as the sorted array.
• Finally the original array is printed and the "bead_sort()" function is called to sort the array. The sorted array is then printed.

Flowchart :

PHP Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Write a PHP program to sort a list of elements using Radix sort.
Next: Write a PHP program to sort a list of elements using Bogo sort.