Introducción a los algoritmos de ordenación (ordenación por burbuja)
from spectrumgirl
La capacidad de ordenar y buscar eficazmente elementos en una estructura de datos compleja es fundamental, ya que muchos algoritmos modernos dependen de ello.
La estrategia adecuada para clasificar y buscar datos dependerá del tamaño, tipo y naturaleza de los mismos, con el fin de obtener una solución eficiente a un problema real.
Los algoritmos de ordenación se utilizan ampliamente en sistemas de almacenamiento y procesamiento de datos distribuidos, donde los registros deben ordenarse y almacenarse periódicamente para poder ser recuperados de manera eficiente. También son esenciales en aplicaciones como bases de datos, motores de búsqueda, análisis de datos y optimización de procesos.
Por ejemplo, cuando una tienda online muestra los productos ordenados por precio o popularidad, está utilizando algoritmos de ordenación para organizar los resultados antes de mostrarlos a la persona.
Ordenación por burbuja
Es uno de los algoritmos más simples (y lentos) utilizados para ordenar una lista de datos.
Se basa en que el valor más alto de una lista de “burbujas” de datos avanza hasta la parte superior (como las burbujas en el agua, de ahí su nombre) a medida que el algoritmo realiza varias pasadas o iteraciones.
Durante cada pasada, el algoritmo compara los elementos consecutivos adyacentes y empuja el valor más alto hasta el índice más alto (la posición final). En otras palabras, el valor más alto de la lista sube a medida que la iteración avanza.
Este tipo de iteración requiere poca memoria en tiempo de ejecución, porque toda la ordenación se produce dentro de la estructura de datos original (lo que se conoce como in-place).
Vamos a ver un ejemplo en PHP de este algoritmo.
En esta función lo que hacemos es pasar el listado de elementos $elements por parámetro y por referencia (de ahí el &), para que la función pueda modificar directamente el array original de elementos.
El primer bucle $iteration representa cada pasada completa. En cada iteración se recorre la lista casi por completo, ya que en cada pasada el elemento más grande queda colocado al final.
Dentro del bucle interno, el índice $index va desde cero hasta el tamaño del array menos uno. Aquí es donde comparamos los elementos adyacentes.
Si el elemento actual es mayor que el elemento siguiente, se intercambian. En caso contrario, se continúa con el siguiente par de elementos hasta que todas las pasadas estén completas y la lista resulte ordenada (en este caso, de menor a mayor).
function bubbleSort(&$elements): void
{
$length = count($elements);
for ($iteration = 1; $iteration < $length; $iteration++) {
for ($index = 0; $index < $length - 1 - $iteration; $index++) {
if ($elements[$index] > $elements[$index + 1]) {
[$elements[$index], $elements[$index + 1]] = [$elements[$index + 1], $elements[$index]];
}
}
}
}
Vamos a poner de ejemplo un listado: 3, 1, 2, 4. La salida tiene que ser: 1,2,3,4
En la primera pasada $iteration=1 y el bucle interno $index =0
3 es mayor que 1 por tanto hace el intercambio → 1,3,2,4
Seguimos en el bucle interno ya que $index < $length - 1 - $iteration
$iteration=1 y $index=1 3 es mayor que 2 así que hace el intercambio → 1,2,3,4
Seguimos en el bucle interno ya que $index < $length - 1 - $iteration
$iteration=1 y $index=2 ahora 3 no es mayor que 4 así que no hace el intercambio y se mantiene como está →1,2,3,4
$iteration =2 e $index=0 pero como ya no se cumple la comparación porque 1 esa menor que 2, ni con $index=1 ya que 2 es menor que 3 y se mantiene como está →1,2,3,4.
$iteration=3 e $index=0 lo que compara 1 que no es menor que 2 y se mantiene como está →1,2,3,4.
Lo que quiere decir que desde que $iteration vale 2 las pasadas han sido innecesarias.
Luego tenemos un algoritmo optimizado que lo que hace es detenerse automáticamente cuando detecta que los elementos ya están ordenados. Porque como has podido comprobar, la versión anterior seguía realizando comparaciones incluso cuando ya estaba ordenada.
function bubbleSortOptimized(&$elements): void
{
$length = count($elements);
for ($iteration = 1; $iteration < $length; $iteration++) {
$swapped = false;
for ($index = 0; $index < $length - 1 - $iteration; $index++) {
if ($elements[$index] > $elements[$index + 1]) {
[$elements[$index], $elements[$index + 1]] = [$elements[$index + 1], $elements[$index]];
$swapped = true;
}
}
if (!$swapped) {
break;
}
}
}
Si hay al menos un intercambio, el valor de $swapped se pone a true, lo que indica que había un par de elementos desordenados. Si al terminar la pasada no hay intercambio (es decir $swapped es false) significa que el array ya está completamente ordenado y el algoritmo se detiene antes, evitando pasadas innecesarias.
