Algoritomos de ordenación de arrays en php

Php ya tiene definidas varias funciones para ordenar arrays tanto por valor como por clave. Para obtener información sobre estas funciones puedes mirar en http://php.net/manual/es/array.sorting.php

En este post no vamos a utilizar esas funciones predefinidas, sino que vamos a crear nuestros propios algoritmos de ordenación. Tan solo vamos a centrarnos en 2 algoritmos de ordenación, uno lento pero sencillo de implementar (burbuja) y otro rápido pero cuya implementación resulta más tediosa (quicksort):

1-Algoritmo burbuja

Este algoritmo es el más sencillo de implementar, pero por contrapartida resulta extremadamente lento. Nos será util para ordenar arrays de pequeño tamaño en los que no se note mucho la diferencia de rendimiento y nos cueste más implementar otro algoritmo.

Ejemplo)

function burbuja($array,$n){

  for($i=1;$i<$n;$i++){
    for($j=0;$j<$n-$i;$j++){
       if($array[$j]>$array[$j+1]){
        $k=$array[$j+1];
        $array[$j+1]=$array[$j];
        $array[$j]=$k; 
      }
    }
  }
   return $array;
}

function main() {

  $arrrayA=array(5,4,3,2,1);
  $arrayB=burbuja($arrayA,sizeof($VectorA));
  for($i=0;$i<sizeof($arrayB);$i++)
    echo $arrayB[$i]."\n";
}

//El código es una adaptación del que puedes encontrar en http://saforas.wordpress.com/2011/01/14/codigo-php-ordenamiento-burbuja/

Este algoritmo realiza siempre el mismo número de comparaciones para ordenar un array de n elementos:

    c(n) =    \cfrac{n^2-n}{2}

El número de intercambios que efectúa depende de como esté ordenado el array que pretendemos ordenar. El peor caso se da cuando el vector esta ordenado en orden inverso.

El orden de complejidad de este algoritmo es siempre de O(n²).

2-Algoritmo Quicksort

Este algoritmo es algo más complejo de entender e implementar, pero es mucho más eficiente que el algorimo burbuja. Lo utilizaremos en arrays de gran tamaño cuando la eficiencia sea un factor crucial.

Ejemplo)

function quicksort($array, $izq, $der )
{
$i = $izq;
$j = $der;
$valor_pivote = $array[ ($izq + $der) /2 ];
do{
  while( ($array[$i] < $valor_pivote) && ($j <= $der) )
  {
    $i++;
  }

  while( ($x < $array[$j]) && ($j > $izq) )
  {
    $j--;
  }

  if( $i <= $j )
  {
    $aux = $array[$i]; $array[$i] = $array[$j]; $array[$j] = $aux;
    $i++;  $j--;
  }

}while( $i <= $j );

if( $izq < $j )
  quicksort( $array, $izq, $j );
if( $i < $der )
  quicksort( $array, $i, $der );

return $array;
}

function main()
{

  $arrayA=array(5,4,3,2,1);

  $arrayB=quicksort($arrayA,0,sizeof($VectorA)-1);
  for($i=0;$i<sizeof($arrayB);$i++)
    echo $arrayB[$i]."\n";

}

//El código es una adaptación del código que puedes encontrar en http://saforas.wordpress.com/2011/01/14/codigo-php-ordenamiento-burbuja/

En el mejor caso el algoritmo tiene un orden de complejidad de O(n·log n).
En el peor caso el orden de complejidad del algoritmo es de O(n²).

Share and Enjoy

  • Facebook
  • Twitter
  • Delicious
  • LinkedIn
  • StumbleUpon
  • Add to favorites
  • Email
  • RSS

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>