Nombre:
Alexandra Maguana
Ciclo: Quinto
“Sistemas”
Ordenación de arrays
PHP tiene
varias funciones que se ocupan de ordenar arrays (matrices) y este documento
existe para ayudar a aclararlo todo.
Las
principales diferencias son:
- Algunas ordenan basados en las key de la array, mientras que otras por los valores: $array['key'] = 'valor';
- Si se mantiene o no la correlación entre las key y los valores después de la clasificación, lo cual puede significar que las key se restablecen numéricamente (0,1,2 ...)
- El orden de la clasificación: alfabético, de menor a mayor (ascendente), de mayor a menor (descendente), numérico, natural, aleatorio o definido por el usuario
- Nota: Todas estas funciones de clasificación actúan directamente sobre la variable de array misma, en lugar de devolver un nuevo array ordenado.
- Si alguna de estas funciones de clasificación evalúa a dos miembros como iguales, entonces el orden no queda definido.
<?php
$fruits = array("d" => "lemon", "a" => "orange", "b" => "banana", "c" => "apple");
asort($fruits);
foreach ($fruits as $key => $val) {
echo "$key = $val\n";
}
?>
$fruits = array("d" => "lemon", "a" => "orange", "b" => "banana", "c" => "apple");
asort($fruits);
foreach ($fruits as $key => $val) {
echo "$key = $val\n";
}
?>
Resultado
c = apple
b = banana
d = lemon
a = orange
Las frutas han sido ordenadas alfabeticamente, y se ha
mantenido el índice asociado con cada
elemento.
elemento.
Métodos de Ordenamiento Hechos en PHP
PHP es un
lenguaje de programación usado en esencia para la creación de páginas web
dinámicas.
El objetivo de este post es entregar una serie de métodos de ordenamiento codificados en PHP como se ha venido haciendo en otros lenguajes de programación. Seria buena idea evaluar el rendimiento con cada uno de los códigos y analizar en que casos es mejor cada uno de ellos, eso les dejo a cuenta suya xD.
El objetivo de este post es entregar una serie de métodos de ordenamiento codificados en PHP como se ha venido haciendo en otros lenguajes de programación. Seria buena idea evaluar el rendimiento con cada uno de los códigos y analizar en que casos es mejor cada uno de ellos, eso les dejo a cuenta suya xD.
Cuestiones
generales
Su
finalidad es organizar ciertos datos (normalmente arrays o ficheros) en un
orden creciente o decreciente mediante una regla prefijada (numérica,
alfabética...). Atendiendo al tipo de elemento que se quiera ordenar puede ser:
-
Ordenación interna: Los datos se encuentran en memoria (ya sean arrays, listas,
etc) y son de acceso aleatorio o directo (se puede acceder a un determinado
campo sin pasar por los anteriores).
-
Ordenación externa: Los datos están en un dispositivo de almacenamiento externo
(ficheros) y su ordenación es más lenta que la interna.
Ordenación
interna
Los
métodos de ordenación interna se aplican principalmente a arrays
unidimensionales. Los principales algoritmos de ordenación interna son:
Selección: Este método consiste en buscar
el elemento más pequeño del array y ponerlo en primera posición; luego, entre
los restantes, se busca el elemento más pequeño y se coloca .
Burbuja: Consiste en comparar pares de
elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados
Ya están
ordenados, pero para comprobarlo habría que acabar esta segunda comprobación y
hacer una tercera.
Si el
array tiene N elementos, para estar seguro de que el array está ordenado, hay
que hacer N-1 pasadas, por lo que habría que hacer (N-1)*(N-i-1) comparaciones,
para cada i desde 1 hasta N-1. El número de comparaciones es, por tanto,
N(N-1)/2, lo que nos deja un tiempo de ejecución..
Inserción
binaria: Es el
mismo método que la inserción directa, excepto que la búsqueda del orden de un
elemento en la sublista ordenada se realiza mediante una búsqueda binaria lo
que en principio supone un ahorro de tiempo. No obstante, dado que para la
inserción sigue siendo necesario un desplazamiento de los elementos, el ahorro,
en la mayoría de los casos, no se produce, si bien hay compiladores que
realizan optimizaciones que lo hacen ligeramente más rápido.
Shell: Es una mejora del método de
inserción directa, utilizado cuando el array tiene un gran número de elementos.
En este método no se compara a cada elemento con el de su izquierda, como en el
de inserción, sino con el que está a un cierto número de lugares (llamado
salto) a su izquierda. Este salto es constante, y su valor inicial es N/2
(siendo N el número de elementos, y siendo división entera). Se van dando
pasadas hasta que en una pasada no se intercambie ningún elemento de sitio.
Entonces el salto se reduce a la mitad, y se vuelven a dar pasadas hasta que no
se intercambie ningún elemento, y así sucesivamente hasta que el salto vale 1.
Ordenación rápida (quicksort): Este método se basa en la
táctica "divide y vencerás" que consiste en ir subdividiendo el array
en arrays más pequeños, y ordenar éstos. Para hacer esta división, se toma un
valor del array como pivote, y se mueven todos los elementos menores que este
pivote a su izquierda, y los mayores a su derecha. A continuación se aplica el
mismo método a cada una de las dos partes en las que queda dividido el array.
Normalmente
se toma como pivote el primer elemento de array, y se realizan dos búsquedas:
una de izquierda a derecha, buscando un elemento mayor que el pivote, y otra de
derecha a izquierda, buscando un elemento menor que el pivote. Cuando se han
encontrado los dos, se intercambian, y se sigue realizando la búsqueda hasta
que las dos búsquedas se encuentran.Por ejemplo, para dividir el array
{21,40,4,9,10,35}, los pasos serían:
{21,40,4,9,10,35}
<-- se toma como pivote el 21. La búsqueda de izquierda a derecha encuantra
el valor 40, mayor que pivote, y la búsqueda de derecha a izquierda encuentra
el valor 10, menor que el pivote. Se intercambian:
{21,10,4,9,40,35} <-- Si seguimos la búsqueda, la primera encuentra el valor 40, y la segunda el valor 9, pero ya se han cruzado, así que paramos. Para terminar la división, se coloca el pivote en su lugar (en el número encontrado por la segunda búsqueda, el 9, quedando:
{9,10,4,21,40,35} <-- Ahora tenemos dividido el array en dos arrays más pequeños: el {9,10,4} y el {40,35}, y se repetiría el mismo proceso.
{21,10,4,9,40,35} <-- Si seguimos la búsqueda, la primera encuentra el valor 40, y la segunda el valor 9, pero ya se han cruzado, así que paramos. Para terminar la división, se coloca el pivote en su lugar (en el número encontrado por la segunda búsqueda, el 9, quedando:
{9,10,4,21,40,35} <-- Ahora tenemos dividido el array en dos arrays más pequeños: el {9,10,4} y el {40,35}, y se repetiría el mismo proceso.
C hay una
función que realiza esta ordenación sin tener que implementarla, llamada qsort
(incluida en stdlib.h):
qsort(nombre_array,número,tamaño,función);
donde nombre_array
es el nombre del array a ordenar, número es el número de elementos del array, tamaño
indica el tamaño en bytes de cada elemento y función es un puntero a una
función que hay que implementar, que recibe dos elementos y devuelve 0 si son
iguales, algo menor que 0 si el primero es menor que el segundo, y algo mayor
que 0 si el segundo es menor que el primero. Por ejemplo, el programa de antes
sería:
, es
mucho más cómodo usar qsort que implementar toda la función, pero hay que tener
mucho cuidado con el manejo de los punteros en la función, sobre todo si se
está trabajando con estructuras.
Intercalación: no es propiamente un método de
ordenación, consiste en la unión de dos arrays ordenados de modo que la unión
esté también ordenada. Para ello, basta con recorrer los arrays de izquierda a
derecha e ir cogiendo el menor de los dos elementos, de forma que sólo aumenta
el contador del array del que sale el elemento siguiente para el array-suma. Si
quisiéramos sumar los arrays {1,2,4} y {3,5,6}, los pasos serían:
Esto se
puede realizar mediante un único recorrido de cada lista, mediante dos punteros
que recorren cada una. En el ejemplo anterior se insertan en este orden -salvo
los dos 6 que puede variar según la implementación-: 0 (lista 2), el 1 (lista
1), el 2 (lista 2), el 3, 5 y 6 (lista 1), el 6 y 7 (lista 2), el 8 y 9 (lista
1), y por llegar al final de la lista 1, se introduce directamente todo lo que
quede de la lista 2, que es el 10.
En la siguiente implementación no se crea una nueva lista realmente, sólo se modifican los enlaces destruyendo las dos listas y fusionándolas en una sola. Se emplea un centinela que apunta a sí mismo y que contiene como clave el valor más grande posible. El último elemento de cada lista apuntará al centinela, incluso si la lista está vacía.
En la siguiente implementación no se crea una nueva lista realmente, sólo se modifican los enlaces destruyendo las dos listas y fusionándolas en una sola. Se emplea un centinela que apunta a sí mismo y que contiene como clave el valor más grande posible. El último elemento de cada lista apuntará al centinela, incluso si la lista está vacía.
- Segunda
parte: divide y vencerás. Se separa la lista original en dos trozos del mismo
tamaño (salvo listas de longitud impar) que se ordenan recursivamente, y una
vez ordenados se fusionan obteniendo una lista ordenada. Como todo algoritmo
basado en divide y vencerás tiene un caso base y un caso recursivo.
* Caso
base: cuando la lista tiene 1 ó 0 elementos (0 se da si se trata de ordenar
una lista vacía). Se devuelve la lista tal cual está.
* Caso
recursivo: cuando la longitud de la lista es de al menos 2 elementos. Se divide
la lista en dos trozos del mismo tamaño que se ordenan recursivamente. Una vez
ordenado cada trozo, se fusionan y se
devuelve la lista resultante.
La
implementación propuesta emplea un centinela sobre la lista inicial que apunte
hacia sí mismo y que además contiene el máximo valor de un entero. La lista
dispone de cabecera y centinela, pero obsérvese como se elimina durante la
ordenación.
Este es
un buen algoritmo de ordenación, pues no requiere espacio para una nueva lista
y sólo las operaciones recursivas consumen algo de memoria. Es por tanto un algoritmo
ideal para ordenar listas.
La
complejidad es la misma en todos los casos, ya que no influye cómo esté
ordenada la lista inicial -esto es, no existe ni mejor ni peor caso-, puesto
que la intercalación de dos listas ordenadas siempre se realiza de una única
pasada. La complejidad es proporcional a N·logN, característica de los
algoritmos "Divide y Vencerás". Para hacer más eficiente el algoritmo
es mejor realizar un primer recorrido sobre toda la lista para contar el número
de elementos y añadir como parámetro a la función dicho número.
BIBLIOGRAFIA
http://www.algoritmia.net/articles.php?id=31
http://saforas.wordpress.com/2011/01/14/metodos-de-ordenamiento-hechos-en-php http://www.php.net/manual/es/function.asort.php
http://saforas.wordpress.com/2011/01/14/metodos-de-ordenamiento-hechos-en-php http://www.php.net/manual/es/function.asort.php
