Ordenación de Arrays con QuickSort en PHP

Implementación de una clase en PHP para la ordenación de arrays por el algoritmo QuickShort.

En este articulo vamos a implementar una clase php que nos permita ordenar arrays con el clasico algoritmo quick short, un algoritmo de ordenacion con una eficiencia en la busqueda muy alta.
En primer lugar la pagina php que nos servirá de ejmeplo para la clase:

ejemplo.php

<?
include('Quicksort.php');
$QS=new Quicksort;
$array=array('8','10','2','1','1','6','5','5','3'); $partido=$QS->QS_ordenaParteArray($array,2,5);

for($i=0;$i<count($partido);$i++)
echo $partido[$i]."n";
echo "n";

$QS->Quick_sort($array,0,count($array)-1);
for($i=0;$i<count($array);$i++)
echo $array[$i]."n";
?>

En primer lugar sacamos la ordenacion del array de ejemplo desde la posicion 2 a la 5. El segundo ejemplo es la ordenacion del array completo.

La clase consta del constructor y de un metodo. El constructor es el metodo de ordenacion en si. El metodo QS_ordenaParteArray ordena un array desde la posicion de inicio que le pidamos hasta la posicion de fin que le indiquemos por parametro.
La ordenacion que se hace en el constructor se basa en el algoritmo recusivo que constituye el quick short. Este algoritmo situa una serie de pivotes en la cadena y ordena la parte de array cogiendo el valor del pivote como referencia para pasar valores a izquierda y derecha de este en funcion de si es menor o mayor. El metodo es recursivo de manera que divide la cadena en sucesivos pivotes hasta que ordena toda la cadena.

Quicksort.php

<?
class Quicksort
{
function Quick_sort(&$array,$inicio,$fin)
{
$mitad=$array[floor(($inicio+$fin)/2)];
$i=$inicio;
$j=$fin;

do
{
while ($array[$i]<$mitad) $i++;
while ($array[$j]>$mitad) $j--;
if ($i<=$j)
{
$temp=$array[$i]; $array[$i]=$array[$j]; $array[$j]=$temp;
$i++; $j--;
}
} while ($i<=$j);

if ($fin<$j) $this->Quick_sort($array, $inicio, $j);
if ($i<$fin) $this->Quick_sort($array, $i, $fin);
}

function QS_ordenaParteArray($array,$inicio,$fin)
{
$temp=array();
for($a=$inicio;$a<=$fin;$a++)
{
$temp[]=$array[$a];
}
$this->Quick_sort($temp,0,count($temp)-1);
return $temp;
}
}
?>

Usuarios que han visto este tema también han visto...

- Evitar que las imagenes deformen tu web
- Conexión con MySQL en PHP
- Control de permisos en PHP con phpGACL
- Eliminar publicidad de los hosting gratuitos
- Paginar los resultados de una consulta PHP

- Versión imprimible de este documento

- Enviar por e-mail este documento