PHP Searching and Sorting Algorithm: Bucket sort

PHP Searching and Sorting Algorithm: Exercise-10 with Solution

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

Sample Solution:

PHP Code:

<?php
// Function to perform insertion sort on an array
function insertion_sort(&$elements, $fn = 'comparison_function') {
  if (!is_array($elements) || !is_callable($fn)) return; // Check if the input is valid
  for ($i = 1; $i < sizeof($elements); $i++) { // Loop through each element starting from the second
    $key = $elements[$i]; // Store the current element to be compared
                          // $key will be the right side element that will be
                          // compared against the left sorted elements. For
                          // min to max sort, $key should be higher than
                          // $elements[0] to $elements[$j]
    
    $j = $i - 1; // Set the index to the previous element
    while ( $j >= 0 && $fn($key, $elements[$j]) ) { // Loop through sorted elements to find the correct position for $key
      $elements[$j + 1] = $elements[$j]; // Shift elements to the right
      $j = $j - 1; // Move to the previous element
    }
    $elements[$j + 1] = $key; // Place $key in its correct position
  }
}

/**
 * Comparison function used to compare each element.
 * @param mixed $a
 * @param mixed $b
 * @returns bool True iff $a is less than $b.
 */
function comparison_function(&$a, &$b) {
  return $a < $b; // Compare if $a is less than $b
}

// Function to perform bucket sort on an array
function bucket_sort(&$elements) {
  $n = sizeof($elements); // Get the size of the array
  $buckets = array(); // Initialize an array to hold buckets
  // Initialize the buckets.
  for ($i = 0; $i < $n; $i++) { // Loop through each element
    $buckets[$i] = array(); // Create an empty bucket
  }
  // Put each element into matched bucket.
  foreach ($elements as $el) { // Loop through each element in the array
    array_push($buckets[ceil($el/10)], $el); // Put the element in the appropriate bucket
  }
  // Sort elements in each bucket using insertion sort.
  $j = 0; // Initialize a variable to keep track of the index
  for ($i = 0; $i < $n; $i++) { // Loop through each bucket
    // Sort only non-empty bucket
    if (!empty($buckets[$i])) { // Check if the bucket is not empty
      insertion_sort($buckets[$i]); // Sort the elements in the bucket
      // Move sorted elements in the bucket into original array.
      foreach ($buckets[$i] as $el) { // Loop through each element in the bucket
        $elements[$j++] = $el; // Move the element to the original array
      }
    }
  }
}

$a = array(-1,0,2,3,-2); // Define the input array
echo "Original Array :\n"; // Print original array label
insertion_sort($a); // Sort the elements
echo "\nSorted Array :\n"; // Print sorted array label
var_dump($a); // Print the sorted array
?>

Output:

Original Array :
array(5) {
  [0]=>
  int(-1)
  [1]=>
  int(0)
  [2]=>
  int(2)
  [3]=>
  int(3)
  [4]=>
  int(-2)
}

Sorted Array :
array(5) {
  [0]=>
  int(-2)
  [1]=>
  int(-1)
  [2]=>
  int(0)
  [3]=>
  int(2)
  [4]=>
  int(3)
}

Explanation:

In the exercise above,

• The code defines two functions: "insertion_sort()" and "bucket_sort()".
• insertion_sort() implements the insertion sort algorithm, which sorts an array in ascending order.
• bucket_sort() implements the bucket sort algorithm, which sorts an array by distributing elements into a number of buckets and then sorting each bucket individually.
• The insertion_sort() function takes an array '$elements' and an optional comparison function '$fn' as arguments. It sorts the array using the insertion sort algorithm based on the comparison function provided. By default, it uses the comparison_function for comparison.
• The comparison_function() is a user-defined function that compares two elements '$a' and '$b' and returns true if '$a' is less than '$b'.
• The "bucket_sort()" function sorts the input array '$elements' using the bucket sort algorithm. It first divides the elements into buckets based on their values, then sorts each bucket using the insertion sort algorithm, and finally combines the sorted buckets to obtain the sorted array.
• The code then defines an input array '$a', sorts it using the "insertion_sort()" function, and prints the sorted array using "var_dump()".

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 Gnome sort.
Next: Write a PHP program to sort a list of elements using Counting sort.