PHP 병합정렬 구현

1 개요[ | ]

PHP 병합정렬 구현

<?php
function merge_sort(&$a) {
    $size = count($a);
    if( $size<2 ) return;
    $bound = intdiv($size,2);
    $L = array_slice($a, 0, $bound);
    $R = array_slice($a, $bound, $size);
    merge_sort( $L );
    merge_sort( $R );
    foreach( $a as &$x ) {
        if(empty($R)) { $x=array_shift($L); continue; }
        if(empty($L)) { $x=array_shift($R); continue; }
        $x = ($R[0]<$L[0])? array_shift($R): array_shift($L);
    }
}
$arr = [9,1,22,4,0,-1,1,22,100,10];
merge_sort( $arr );
echo implode(',',$arr);
# -1,0,1,1,4,9,10,22,22,100

<?php
function merge_sort(&$a, $left=0, $right=null) {
    if( is_null($right) ) $right=count($a)-1;
    if( $left>=$right ) return;
    $middle = intdiv($left+$right-1, 2);
    merge_sort($a, $left, $middle);
    merge_sort($a, $middle+1, $right);
    $n1 = $middle + 1 - $left;
    $n2 = $right - $middle;
    $L = array_fill(0, $n1, 0);
    $R = array_fill(0, $n2, 0);
    for($i=0; $i<$n1; $i++) $L[$i] = $a[$left+$i];
    for($i=0; $i<$n2; $i++) $R[$i] = $a[$middle+1+$i];
    $k = $left;
    $i = $j = 0;
    while( $i<$n1 && $j<$n2 ) {
        if( $L[$i]<=$R[$j] ) { $a[$k] = $L[$i]; $i++; $k++; }
        else { $a[$k] = $R[$j]; $j++; $k++; }
    }
    while( $i<$n1 ) { $a[$k]=$L[$i]; $i++; $k++; }
    while( $j<$n2 ) { $a[$k]=$R[$j]; $j++; $k++; }
}
$arr = [9,1,22,4,0,-1,1,22,100,10];
merge_sort( $arr );
echo implode(',',$arr);
# -1,0,1,1,4,9,10,22,22,100

<?php
function merge_sort(&$a, $left=0, $right=null) {
    $merge = function(&$a, $left, $middle, $right) {
        $n1 = $middle + 1 - $left;
        $n2 = $right - $middle;
        $L = array_fill(0, $n1, 0);
        $R = array_fill(0, $n2, 0);
        for($i=0; $i<$n1; $i++) $L[$i] = $a[$left+$i];
        for($i=0; $i<$n2; $i++) $R[$i] = $a[$middle+1+$i];
        $k = $left;
        $i = $j = 0;
        while( $i<$n1 && $j<$n2 ) {
            if( $L[$i]<=$R[$j] ) { $a[$k] = $L[$i]; $i++; $k++; }
            else { $a[$k] = $R[$j]; $j++; $k++; }
        }
        while( $i<$n1 ) { $a[$k]=$L[$i]; $i++; $k++; }
        while( $j<$n2 ) { $a[$k]=$R[$j]; $j++; $k++; }
    };
    if( is_null($right) ) $right=count($a)-1;
    if( $left>=$right ) return;
    $middle = intdiv($left+$right-1, 2);
    merge_sort($a, $left, $middle);
    merge_sort($a, $middle+1, $right);
    $merge($a, $left, $middle, $right);
}
$arr = [9,1,22,4,0,-1,1,22,100,10];
merge_sort( $arr );
echo implode(',',$arr);
# -1,0,1,1,4,9,10,22,22,100

2 같이 보기[ | ]