PHP Searching and Sorting Algorithm: Counting sort

PHP Searching and Sorting Algorithm: Exercise-11 with Solution

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

According to Wikipedia "In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently".

The algorithm loops over the items, computing a histogram of the number of times each key occurs within the input collection. It then performs a prefix sum computation (a second loop, over the range of possible keys) to determine, for each key, the starting position in the output array of the items having that key. Finally, it loops over the items again, moving each item into its sorted position in the output array.

Sample Solution :

PHP Code :

<?php
// Function to perform counting sort on an array
function counting_sort($my_array, $min, $max)
{
  $count = array(); // Initialize an array to store count of each element
  for($i = $min; $i <= $max; $i++) // Iterate over the range from min to max
  {
    $count[$i] = 0; // Initialize each count to zero
  }
 
  foreach($my_array as $number) // Iterate over the input array
  {
    $count[$number]++; // Increment the count of the current element
  }
  $z = 0; // Initialize a variable to keep track of the current index
  for($i = $min; $i <= $max; $i++) { // Iterate over the range from min to max
    while( $count[$i]-- > 0 ) { // Decrement the count of the current element until it becomes zero
      $my_array[$z++] = $i; // Fill the original array with the current element
    }
  }
  return $my_array; // Return the sorted array
}
$test_array = array(3, 0, 2, 5, -1, 4, 1); // Define the input array
echo "Original Array :\n"; // Print original array label
echo implode(', ',$test_array ); // Print the original array
echo "\nSorted Array\n:"; // Print sorted array label
echo implode(', ',counting_sort($test_array, -1, 5)). PHP_EOL; // Sort the array using counting sort and print the sorted array
?>

Output:

Original Array :                                                    
3, 0, 2, 5, -1, 4, 1                                                
Sorted Array :                                                      
-1, 0, 1, 2, 3, 4, 5    

Explanation:

In the exercise above,

• The "counting_sort()" function takes three parameters: the array to be sorted ($my_array), the minimum value in the array ($min), and the maximum value in the array ($max).
• Inside the function, an array named '$count' is initialized to store the count of each element in the input array.
• Then, a loop iterates over the range from '$min' to '$max', initializing each count to zero.
• Next, a "foreach" loop iterates over the input array '$my_array', incrementing the count of each element in the '$count' array.
• After counting the occurrences of each element, another loop iterates over the range from '$min' to '$max'. Within this loop, another inner loop is used to fill the original array '$my_array' with the sorted elements based on their counts.
• Finally, a sorted array is 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 Bucket sort.
Next: Write a PHP program to sort a list of elements using Radix sort.