Implementation code of php counting sorting algorithm (with four example codes)

Count sorting is only suitable for use when the change of keys is not greater than the total number of elements. It is often used as a subroutine of another sorting algorithm (cardinality sorting), which can effectively handle larger keys.

In short, count sorting is a stable linear time sorting algorithm. Count sorting uses an extra array C, where the i-th element is the number of elements with a value equal to i in the array A to be sorted. Then, according to array C, the elements in A are arranged to the correct position.

The usual implementation steps of counting and sorting algorithm are:

1. Find the largest and smallest elements in the array to be sorted;

2. Statistics the number of times each element with a value of i in the array appears and save it into the i-th item of array C;

3. Accumulate all counts (starting from the first element in C, each item and the previous item are added);

4. Reversely fill the target array: Place each element i in the C[i]th item of the new array, and subtract C[i] by 1 for each element.

The implementation code example of PHP counting sorting algorithm is as follows:

&lt;?php
function counting_sort($my_array, $min, $max)
{
  $count = array();
  for($i = $min; $i &lt;= $max; $i++)
  {
    $count[$i] = 0;
  }
 
  foreach($my_array as $number)
  {
    $count[$number]++;
  }
  $z = 0;
  for($i = $min; $i &lt;= $max; $i++) {
    while( $count[$i]-- &gt; 0 ) {
      $my_array[$z++] = $i;
    }
  }
  return $my_array;
}
$test_array = array(3, 0, 2, 5, -1, 4, 1);
echo "Raw Array:\n";
echo implode(', ',$test_array );
echo "\nSorted array\n:";
echo implode(', ',counting_sort($test_array, -1, 5)). PHP_EOL;

Output:

Original array: 3, 0, 2, 5, -1, 4, 1

Sort array:-1, 0, 1, 2, 3, 4, 5

Here is an example

1. Count sorting is only applicable to integer sorting in small ranges.

<?php
$arr = [95,94,91,98,99,90,99,93,91,92];
function countSort($arr){
$max = $arr[0];
$min = $arr[0];
for($i=0;$i<count($arr);$i++){
if($arr[$i]>$max){
$max = $arr[$i];
}
if($arr[$i] < $min){
$min = $arr[$i];
}
}
try{
$frequency = new SplFixedArray($max-$min+1);
for($i=0;$i<count($arr);$i++){
if(empty($frequency[$arr[$i]-$min]))
$frequency[$arr[$i]-$min] = 0;
$frequency[$arr[$i]-$min] += 1;
}

$sum = 0;
for ($i=0; $i < count($frequency); $i++) {
$sum += $frequency[$i];
$frequency[$i] = $sum;
}

$splfixed = new SplFixedArray(count($arr));

for($i=(count($arr)-1);$i>=0;$i--){
$splfixed[$frequency[$arr[$i]-$min]-1] = $arr[$i];
$frequency[$arr[$i]-$min] -= 1;
}
}catch(RuntimeException $re){
echo "RuntimeException: ".$re->getMessage()."\n";
}
print_r($splfixed->toArray());
}
countSort($arr);
?>

Output

Array
(
    [0] => 90
    [1] => 91
    [2] => 91
    [3] => 92
    [4] => 93
    [5] => 94
    [6] => 95
    [7] => 98
    [8] => 99
    [9] => 99
)

2. PHP count sorting

Get the minimum value min and maximum value in the sequence max O(n)
Statistics the number of occurrences of all values between max in the sequence O(n)
Sequential output of min - all values of max, no output is output if the number of times is 0, and the number of other times is output as much as the number of times is O(k) k is the data range

For example, the sequence is: 2, 4, 6, 9, 4, 8

min = 2, max = 9, n is 6, k is 8

The number of occurrences is

[2 => 1, 3 => 0, 4 => 2, 5 => 0, 6 => 1, 7 => 0, 8 => 1, 9 => 1]

The output result is

2, 4, 4, 6, 8, 9

It is obvious that the complexity of count sorting is O(n) + O(k), which is related to the amount of data and the data range.
If n and k are close, it can be considered O(n)
At the same time, because the number of occurrences is to be counted, if the data range is too large and the data is sparse, the space waste will be relatively large.

class CountSort
{
  private $originalData = [];
  private $rangeMap = [];
  private $resultData = [];

  public function __construct($original = [])
  {
    $this->originalData = $original;
  }

  public function sort()
  {
    list($min, $max) = $this->calculateDataRange();
    $this->statisticNumberOfOccurrence($min, $max);
    $this->resultData = $this->generateResult();
    return $this->resultData;
  }

  protected function calculateDataRange()
  {
    $max = null;
    $min = null;

    foreach ($this->originalData as $value) {
      if (!is_null($max)) {
        if ($value > $max) {
          $max = $value;
        }
      } else {
        $max = $value;
      }

      if (!is_null($min)) {
        if ($value < $min) {
          $min = $value;
        }
      } else {
        $min = $value;
      }
    }

    return [$min, $max];
  }

  protected function statisticNumberOfOccurrence($min, $max)
  {
    for ($i = $min; $i <= $max; $i++) {
      $this->rangeMap[$i] = 0;
    }

    foreach ($this->originalData as $value) {
      $this->rangeMap[$value]++;
    }
  }

  protected function generateResult()
  {
    $result = [];

    foreach ($this->rangeMap as $key => $value) {
      if ($value != 0) {
        for ($i = 0; $i < $value; $i++) {
          array_push($result, $key);
        }
      }
    }
    return $result;
  }
}

$testData = [2, 3, 4, 3, 10, 30, 20, 15, 10, 12, 33];

$countSort = new CountSort($testData);
echo '<pre>';
var_dump($countSort->sort());

Output

<pre>array(11) {
[0]=>
int(2)
[1]=>
int(3)
[2]=>
int(3)
[3]=>
int(4)
[4]=>
int(10)
[5]=>
int(10)
[6]=>
int(12)
[7]=>
int(15)
[8]=>
int(20)
[9]=>
int(30)
[10]=>
int(33)
}

This is the end of this article about the implementation code of the php counting sorting algorithm. For more related php counting sorting content, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!