PHP Searching and Sorting Algorithm: Radix sort

PHP Searching and Sorting Algorithm: Exercise-12 with Solution

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

Sample Solution :

PHP Code :

<?php
// Function to perform radix sort on an array
function radix_sort(&$elements) {
  // Array for 10 queues.
  $queues = array_fill(0, 10, array());
  // Find the maximum number of digits in the array
  $max_digits = strlen((string) max($elements));
  // Iterate over each digit position
  for ($i = 0; $i < $max_digits; $i++) {
    // Distribute elements into queues based on the current digit
    foreach ($elements as $el) {
      $digit = (int) str_pad((string) ($el / pow(10, $i)) % 10, 1, '0', STR_PAD_LEFT);
      array_push($queues[$digit], $el);
    }
    // Reconstruct the array from the queues
    $elements = array_reduce($queues, 'array_merge', array());
    // Clear queues for next iteration
    $queues = array_fill(0, 10, array());
  }
}

// Example usage:
$a = array(170, 45, 75, 90, 802, 24, 2, 66); // Define an example array
echo 'Original Array : ' . implode(', ', $a) . "\n";

radix_sort($a); // Sort the array using radix sort
echo "\nSorted Array:\n";
echo 'Original Array : ' . implode(', ', $a) . "\n";
?>

Output:

Original Array : 170, 45, 75, 90, 802, 24, 2, 66

Sorted Array:
Original Array : 2, 24, 45, 66, 75, 90, 170, 802

Explanation:

In the exercise above,

• radix_sort function: This function takes an array of integers as input and sorts it using the radix sort algorithm.
• $elements: This parameter represents the array of integers to be sorted. It's passed by reference (&) to allow modifications to the original array.
• $queues: This array stores 10 queues (buckets), one for each digit (0 to 9).
• $max_digits: It calculates the maximum number of digits among all the elements in the array. This is used to determine the number of iterations needed for the radix sort.
• for loop: It iterates over each digit position starting from the least significant digit (rightmost) to the most significant digit (leftmost).
• Inner foreach loop: This loop distributes the elements into queues based on the current digit being considered. It calculates the digit by performing integer division and modulo operations.
• array_push: It adds the element to the corresponding queue based on the calculated digit.
• Reconstruction of the array: After distributing all elements into queues for the current digit position, the elements are reconstructed by merging all queues. This is done using the "array_reduce()" function with the "array_merge()" callback.
• Clear queues: The queues are cleared after each iteration to prepare them for the next digit position.
• Finally, the original and a sorted array are returned.

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