【アルゴリズム】PHP実現クラシックアルゴリズム(下)

前言
先日,PHPにより異なるソートアルゴリズムを実現し,アルゴリズムに対応する時間消費を比較した.【アルゴリズム】PHP実現クラシックアルゴリズム(上)
次のアルゴリズムを実装します

スタックソート

カクテルソート

直接選択ソート

カウントソート

CODE

$arr = [];

for ($i = 0; $i < 5000; $i++) {
    $arr[] = rand(1, 50000);
}



// 5    

/** *          * @param $a * @param $b */
function swap(&$a,&$b){
    $temp = $b;
    $b = $a;
    $a = $temp;
}

/** *     * @param $i * @return mixed */
function lchild($i){ return $i*2+1;}

/** *     * @param $i * @return mixed */
function rchild($i){ return $i*2+2;}

/** *      * @param $array         * @param $i             * @param $heapsize       */
function build_heap(&$array,$i,$heapsize){

    $left = lchild($i);
    $right = rchild($i);
    $max = $i;
    //                 ,       
    if($i < $heapsize && $left < $heapsize  && $array[$left] > $array[$i] ){
        $max = $left;
    }

    //                    ,       
    if($i < $heapsize && $right < $heapsize && $array[$right] > $array[$max]){
        $max = $right;
    }

    //         ,           
    if($i != $max && $i < $heapsize && $max < $heapsize){

        //        ,         
        swap($array[$i],$array[$max]);
        build_heap($array,$max,$heapsize);

    }
}

/** *        * @param $array        * @param $heapsize       */
function sortHeap(&$array,$heapsize){
    while($heapsize){ //      0

        //                   
        swap($array[0],$array[$heapsize-1]);
        $heapsize = $heapsize -1;
        build_heap($array,0,$heapsize); //              ,            
    }
}

/** *     * @param $array * @param $heapsize */
function createHeap(&$array,$heapsize){
    $i = ceil($heapsize/2)-1; //       
    for( ; $i>=0 ;$i-- ){  //         
        build_heap($array,$i,$heapsize);
    }
}

/** *        */
function Heapsort($array){
    $heapsize = count($array);
    createHeap($array,$heapsize);
    sortHeap($array,$heapsize);

    return $array;

}



$heapsort_start_time = microtime(true);

$heapsort_sort = Heapsort($arr);

$heapsort_end_time = microtime(true);

$heapsort_need_time = $heapsort_end_time - $heapsort_start_time;

print_r("     :" . $heapsort_need_time . "<br />");


// 6       

/** *       * @param $arr * @return mixed */
function Cocktailsort($arr) {
    $arr_len  =count($arr);

    for($i = 0 ; $i < ($arr_len/2) ; $i ++){
        //        
        for( $j = $i ; $j < ( $arr_len - $i - 1 ) ; $j ++ ){
            if($arr[$j] < $arr[$j + 1] ){
                swap($arr[$j],$arr[$j + 1]);
            }
        }
        //        
        for($j = $arr_len - 1 - ($i + 1); $j > $i ; $j --){
            if($arr[$j] > $arr[$j - 1]){
                swap($arr[$j],$arr[$j - 1]);
            }
        }
    }
    return $arr;
}

$cocktailsort_start_time = microtime(true);

$cocktailsort_sort = Cocktailsort($arr);

$cocktailsortt_end_time = microtime(true);

$cocktailsort_need_time = $cocktailsortt_end_time - $cocktailsort_start_time;

print_r("       :" . $cocktailsort_need_time . "<br />");


// 7     

/** *      * @param $arr */
function Shellsort($arr) {
    $n=count($arr); //    

    for($gap=floor($n/2);$gap>0;$gap=floor($gap/=2)) //
    {
        for($i=$gap;$i<$n;++$i) //      
        {
            //          
            for( $j=$i-$gap; $j>=0 && $arr[$j+$gap] < $arr[$j]; $j -= $gap)
            {
                swap($arr[$j],$arr[$j+$gap]);
            }
        }
    }

    return $arr;
}

$shellsort_start_time = microtime(true);

$shellsort_sort = Cocktailsort($arr);

$shellsort_end_time = microtime(true);

$shellsort_need_time = $shellsort_end_time - $shellsort_start_time;

print_r("      :" . $shellsort_need_time . "<br />");

// 8       

/** *        * @param $arr * @return mixed */
function Straightselectsort($arr){

    $n = count($arr);

    for($i = 0 ; $i < $n - 1;$i++){
        $m = $i;
        for($j = $i+1 ; $j < $n; $j++){
            if($arr[$j] < $arr[$m] ){
                $m = $j;
            }

            if($m != $j){
                //    
                swap($arr[$m],$arr[$j]);
            }
        }
    }
    return $arr;
}

$straightselectsort_start_time = microtime(true);

$straightselectsort_sort = Cocktailsort($arr);

$straightselectsort_end_time = microtime(true);

$straightselectsort_need_time = $straightselectsort_end_time - $straightselectsort_start_time;

print_r("        :" . $straightselectsort_need_time . "<br />");


// 9     

/** *      * @param $arr * @return mixed */
function Countsort($arr){

    $max = $arr[0];
    $min = $arr[0];

    foreach($arr as $key => $value) {
        if ($value > $max) {
            $max = $value;
        }
        if ($value < $min) {
            $min = $value;
        }
    }
        //  k           ，        +1
        $c=[];
        $k = $max - $min + 1;
        for($i = 0; $i < count($arr) ; $i ++){
            $c[$arr[$i] - $min ] +=1;
        }

        for($i=1;$i < count($c); ++$i){
            $c[$i] = $c[$i] + $c[$i - 1];
        }

        for($i = count($arr);$i > 0 ; --$i){
            $b[ -- $c[$arr[$i] - $min] ] = $arr[$i];
        }

    return $b;
}

$countsort_start_time = microtime(true);

$countsort_sort = Cocktailsort($arr);

$countsort_end_time = microtime(true);

$countsort_need_time = $countsort_end_time - $countsort_start_time;

print_r("      :" . $countsort_need_time . "<br />");

時間の比較
スタックソート時間:0.086709976196289カクテルソート時間:4.667659473419ヒルソート時間:4.4215688705444直接選択ソート時間:4.5292422044754カウントソート時間:4.260107004053
参考資料

アルゴリズム導論