Métodos de ordenación

order-methods.php

<?php

set_time_limit(0);
ini_set('memory_limit','128M');

function burbuja ($v,&$metodo) {
    $tmp = $v[0];
    $N = count($v);
    
    $metodo['burbuja']['tiempo'] = microtime(true);
    
    do {
        $movimientos = 0;
        
        for ($n=1;$n<$N;$n++) {
            $metodo['burbuja']['comparaciones']++;
            
            if ($v[$n] < $v[$n-1]) {
                $movimientos++;
                $metodo['burbuja']['movimientos']++;
                
                $tmp = $v[$n];
                $v[$n] = $v[$n-1];
                $v[$n-1] = $tmp;
            }
        }
    }
    while ($movimientos > 0);
    
    $metodo['burbuja']['tiempo'] = microtime(true) - $metodo['burbuja']['tiempo'];
    $metodo['burbuja']['v'] = $v;
}

function seleccion ($v,&$metodo) {
    $metodo['seleccion']['tiempo'] = microtime(true);
    
    $nuevo = array();
    
    do {
        $N = count($v);
        $menor = $v[0];
        $borrar = 0;
        
        for ($n=1;$n<$N;$n++) {
            $metodo['seleccion']['comparaciones']++;
            
            if ($menor > $v[$n]) {
                $menor = $v[$n];
                $borrar = $n;
            }
        }
        
        $metodo['seleccion']['movimientos']++;
        $nuevo[] = $menor;
        unset($v[$borrar]);
        $v = array_merge(array(),$v);
    }
    while ($N);
    
    $metodo['seleccion']['tiempo'] = microtime(true) - $metodo['seleccion']['tiempo'];
    $metodo['seleccion']['v'] = $nuevo;
}

function quicksort ($v,&$metodo) {
    $metodo['quicksort']['tiempo'] = microtime(true);
    _quicksort($v,$metodo);
    
    $metodo['quicksort']['tiempo'] = microtime(true) - $metodo['quicksort']['tiempo'];
    $metodo['quicksort']['v'] = $v;
}

function _quicksort (&$v,&$metodo,$inicio=0,$fin=false) {
    if ($fin === false) {
        $fin = count($v) - 1;
    }
    
    if ($fin - $inicio < 1) {
        return;
    }
    
    $pos = $inicio;
    $actual = $v[$pos];
    
    for ($n=$inicio+1;$n<=$fin;$n++) {
        $metodo['quicksort']['comparaciones']++;
        
        if (($n < $pos) && ($v[$n] > $actual)) {
            $metodo['quicksort']['movimientos']++;
            shift($v,$pos,$n);
            $pos--;
        }
        else if (($n > $pos) && ($v[$n] < $actual)) {
            $metodo['quicksort']['movimientos']++;
            unshift($v,$pos,$n);
            $pos++;
        }
    }
    
    _quicksort($v,$metodo,$inicio,$pos-1);
    _quicksort($v,$metodo,$pos+1,$fin);
    
    return $v;
}

function shift (&$v,$pivote,$desplazado) {
    if ($desplazado >= $pivote) {
        return;
    }
    
    $valor = $v[$desplazado];
    
    for ($n=$desplazado;$n<$pivote;$n++) {
        $v[$n] = $v[$n+1];
    }
    
    $v[$pivote] = $valor;
}

function unshift (&$v,$pivote,$desplazado) {
    if ($desplazado <= $pivote) {
        return;
    }
    
    $valor = $v[$desplazado];
    
    for ($n=$desplazado;$n>$pivote;$n--) {
        $v[$n] = $v[$n-1];
    }
    
    $v[$pivote] = $valor;
}

function graficar ($v,$metodo) { ?>
    <style type="text/css">
    .marco
    {height:120px;
    margin-bottom:5px;
    border:1px solid #ccc;
    position:relative;}
    
    .leyenda
    {opacity:0.5;
    font-family:sans-serif;
    font-weight:bold;
    padding:3px;}
    
    .leyenda p
    {font-size:small;}
    
    .b /* b - barra*/
    {position:absolute;
    bottom:0;
    width:1px;
    background-color:#ff5a00;}
    </style>
    <div class="marco">
        <div class="leyenda">Original</div>
    <?php foreach ($v as $offset=>$height) { ?>
        <div class="b" style="right:<?php echo (998-$offset) ?>px;height:<?php echo $height ?>px;"></div>
    <?php } ?>
    </div>
    <?php foreach ($metodo as $nombre=>$array) { ?>
        <div class="marco">
            <div class="leyenda"><?php echo ucwords($nombre) ?>
                <p>
                    <?php echo number_format($array['comparaciones'],0,'.',',') ?> comparaciones<br>
                    <?php echo number_format($array['movimientos'],0,'.',',') ?> movimientos<br>
                    <?php echo number_format($array['tiempo']*1000,4,'.',',') ?> milisegundos de ejecuci&oacute;n<br>
                </p>
            </div>
        <?php foreach ($array['v'] as $offset=>$height) { ?>
            <div class="b" style="right:<?php echo (998-$offset) ?>px;height:<?php echo $height ?>px;"></div>
        <?php } ?>
        </div>
    <?php } ?>
    <hr/>
<?php
}


$va = array(array(),array(),array());

for ($n=1;$n<1000;$n++) {
    $va[2][] = ceil($n/10);
    $va[1][] = 100 - floor($n/10);
    $va[0][] = rand(1,100);
}

foreach ($va as &$v) {
    $metodo = array(
        'burbuja' => array(
            'comparaciones' => 0,
            'movimientos' => 0,
            'tiempo' => 0,
        ),
        'quicksort' => array(
            'comparaciones' => 0,
            'movimientos' => 0,
            'tiempo' => 0,
        ),
        'seleccion' => array(
            'comparaciones' => 0,
            'movimientos' => 0,
            'tiempo' => 0,
        ),
    );
    
    burbuja($v,$metodo);
    seleccion($v,$metodo);
    quicksort($v,$metodo);
    
    graficar($v,$metodo);
}

?>