Continuación Vectores

Ordenamiento Burbuja (Bubble Sort)

El ordenamiento burbuja es uno de los métodos más sencillos para organizar los elementos de un vector o arreglo (por ejemplo, números o letras) en orden ascendente o descendente.

Su nombre "burbuja" viene de la idea de que los valores más grandes "suben" poco a poco hacia el final del vector, igual que las burbujas suben hacia la superficie del agua.

Cómo funciona paso a paso

Imagina que tienes este vector de números desordenados:
[5, 2, 9, 1, 3]

El algoritmo compara dos elementos vecinos y los intercambia si están en el orden incorrecto.
Este proceso se repite varias veces hasta que todo el vector queda ordenado.

Veámoslo paso a paso:

1. Compara el primer par (5 y 2).

   • Como 5 > 2, se intercambian → [2, 5, 9, 1, 3]

2. Luego compara 5 y 9.

   • Están en orden, no se cambia nada.

3. Compara 9 y 1.

   • 9 > 1 → se intercambian → [2, 5, 1, 9, 3]

4. Compara 9 y 3.

   • 9 > 3 → se intercambian → [2, 5, 1, 3, 9]

Al terminar la primera pasada, el número 9 (el mayor) ya está en su posición final, al final del vector.

El proceso se repite con los demás elementos, hasta que no haya más intercambios.
Finalmente, el vector quedará así:
[1, 2, 3, 5, 9]

Idea clave

El algoritmo revisa el vector varias veces, comparando pares de elementos vecinos y corrigiendo su posición cuando es necesario.
Aunque no es el método más rápido para grandes cantidades de datos, es ideal para aprender cómo funciona el proceso de comparación e intercambio.

Ventajas

• Muy fácil de entender e implementar.

• Permite visualizar el proceso de ordenamiento paso a paso.

Desventajas

• Es lento para vectores grandes, porque realiza muchas comparaciones innecesarias.

• Su complejidad es O(n²) (cuadrática).

Descargar el libro en Excel se encuentra a continuación y Ubicarse en la Hoja Ordenamiento Burbuja y realizar la prueba de escritorio. 

Presione Clic para descargar el Seudocódigo en PSeInt

Realice seguimiento a la función burbuja teniendo en cuenta la información anterior sobre ordenamiento burbuja.

Ordenamiento Burbuja Mejorado

El ordenamiento burbuja mejorado (o bubble sort optimizado) es una versión más eficiente del algoritmo burbuja clásico.
Aunque el método tradicional es muy fácil de entender, tiene un problema: sigue recorriendo todo el vector incluso cuando ya está ordenado, haciendo comparaciones innecesarias.

El burbuja mejorado soluciona este problema agregando un control o bandera (variable booleana) que detecta si durante una pasada se realizó algún intercambio.

Idea principal

En el ordenamiento burbuja normal:

• Se hacen varias pasadas por el vector.

• En cada pasada se comparan elementos adyacentes.

• Sin importar si ya está ordenado, se sigue revisando hasta el final.

En el burbuja mejorado, agregamos una bandera llamada "cambio" o "intercambio":

• Al iniciar cada pasada, un swiche  (sw) se pone en 0.

• Cada vez que se intercambian dos elementos, se cambia el swiche a 1.

• Al finalizar una pasada, si no hubo ningún intercambio, significa que el vector ya está ordenado, y el algoritmo puede detenerse antes de tiempo.

Ejemplo ilustrativo

Supongamos que tenemos el vector:
[1, 2, 3, 4, 5]

En el burbuja clásico, el algoritmo haría todas las pasadas (4 en total).
Pero en el burbuja mejorado, en la primera pasada no se haría ningún intercambio, por lo tanto, el programa detecta que ya está ordenado y se detiene inmediatamente.

Esto ahorra tiempo y hace que el algoritmo sea más eficiente, especialmente cuando los datos ya están casi ordenados.

Ventajas del Burbuja Mejorado

• Reduce el número de comparaciones innecesarias.

• Termina antes si el vector ya está ordenado.

• Es igual de fácil de entender que el burbuja clásico.

Resumen

El ordenamiento burbuja mejorado mantiene la lógica del método original —comparar e intercambiar elementos vecinos— pero agrega inteligencia al proceso al detenerse cuando detecta que el vector ya está ordenado.
Esto lo convierte en un excelente ejemplo de cómo una pequeña mejora en la lógica puede hacer un algoritmo más eficiente sin complicarlo.

Descargar el libro en Excel se encuentra a continuación y Ubicarse en la Hoja Ordenamiento burbuja mejorado y realizar la prueba de escritorio. 

Presione Clic para descargar el Seudocódigo en PSeInt

Realice seguimiento a la función burbuja teniendo en cuenta la información anterior sobre ordenamiento burbuja. 

Búsqueda Binaria 

La búsqueda binaria es un método eficiente para encontrar un dato dentro de un vector (o arreglo) que está ordenado de menor a mayor (o de mayor a menor).

Imagina que tienes una lista de números ya organizados, por ejemplo:
[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

Y quieres saber si el número 23 está en esa lista.

En lugar de revisar uno por uno (como hace la búsqueda secuencial), la búsqueda binaria divide la lista por la mitad en cada paso, reduciendo muchísimo el número de comparaciones.

Cómo funciona paso a paso

1. Se busca el elemento que está en la mitad del vector.

   • En este caso, el número de la mitad es 16.

2. Se compara con el número que estamos buscando (23).

   • Si son iguales → ¡listo! ya encontramos el elemento.

   • Si el número buscado es mayor, significa que debe estar a la derecha (en la parte de los números más grandes).

   • Si es menor, entonces está a la izquierda (en la parte de los números más pequeños).

3. Se repite el proceso, pero solo con la mitad que corresponde.

   • En este ejemplo, como 23 es mayor que 16, buscamos en la parte derecha del vector.

4. En la siguiente mitad, el número central es 38.

   • Como 23 es menor que 38, buscamos ahora en la parte izquierda de esa mitad.

   • Así seguimos hasta encontrar el número o determinar que no está.

Ventajas

• Mucho más rápida que la búsqueda secuencial cuando el vector es grande.

• Reduce el número de comparaciones a la mitad en cada paso.

• Su complejidad es O(log₂ n) (logarítmica).

Condición importante

La búsqueda binaria solo funciona si el vector está ordenado.
Si los datos no están en orden, el algoritmo no puede "saber" en qué mitad buscar.

Descargar el libro en Excel se  encuentra a continuación y Ubicarse en la Hoja Búsqueda Binaria y realizar la prueba de escritorio.

Presione Clic para descargar el Seudocódigo en PSeInt

Realice seguimiento a la función Busqueda_binaria teniendo en cuenta la información anterior sobre búsqueda binaria en un vector.