counting sort


See On Github

Data

Contributor

Generic placeholder thumbnail

by mitogh

in php

Source Code

<?php
/**
 * Counting Sort Algirithm 
 *
 * @param   Array   $array  The original array
 * @return  Array   $order  The order array
 */
function counting_sort($array = []){
    // Return [] if the array has no elements
    if( !is_array($array) || !count($array) ){
        return $array;
    }
    
    // Find the min and max value
    $max = max($array);
    $min = min($array);
    
    // Fill the aux array from min to max with 0
    $aux = [];
    $aux = array_fill($min, $max, 0);

    foreach($array as $element){
        $aux[$element]++;
    }

    // Fill the order array
    $order = [];
    foreach($aux as $key => $value){
        $i = 0; 
        while($i++ < $value){
            array_push($order, $key);
        }
    }
    return $order;
}
<?php 

require 'counting_sort.php'; 

class CountingSortTest extends PHPUnit_Framework_TestCase{

    public function testNoParameters(){
        $this->assertEmpty(counting_sort([]));
    }

    public function testArrayWithUnorderElements(){
        $original = [3,5,7,1,5,1,2,3,2,71,2,3,4,71,47,7];
        $copy = [3,5,7,1,5,1,2,3,2,71,2,3,4,71,47,7];
        sort($copy, SORT_NUMERIC);

        $this->assertEquals(counting_sort($original), $copy);
    } 
    
    public function testArrayWithOrderelements(){
        $original = [0,1,2,3,4,5,6,7,8,9,10];
        $copy = [0,1,2,3,4,5,6,7,8,9,10];
        
        $this->assertEquals(counting_sort($original), $copy);
    } 

    public function testArrayWithRepeatedElements(){
        $original = [1,1,1,1,1,1,1,1,1,1,1];
        $copy = [1,1,1,1,1,1,1,1,1,1,1];
        $this->assertEquals(counting_sort($original), $copy);
    }
}