Artículo fuente
El algoritmo de ordenamiento burbuja - DEV Community
Maximilian
Introducción
Recientemente tomé un curso de estructuras de datos y algoritmos como parte de mi búsqueda por aprender conceptos de programación de bajo nivel y ciencias de la computación. Como dice el refrán, la mejor manera de consolidar tu conocimiento sobre algo es enseñarlo, y como ya he llenado mi cuota de aburrir a mi pareja con charlas de programación por el mes (probablemente el año), pensé en escribir una serie de publicaciones con algunas de las cosas que he aprendido. Esta es una de esas publicaciones.
¿Qué es el algoritmo de ordenamiento burbuja?
El algoritmo de ordenamiento burbuja se aplica normalmente donde se prefiere la simplicidad sobre la eficiencia. Tiene una complejidad temporal de O(n^2), que no es lo ideal cuando se trata con listas más grandes.
¿Cómo funciona?
Para explicar cómo funciona, aquí hay un pseudocódigo:
for pointer1 in list
for pointer2 in list
if list[j] > list[j + 1]
swap list[j] and list[j + 1]
pointer2++
pointer1++
La idea de este algoritmo es 'hacer burbujear' los elementos más grandes de la lista hasta el final. Podemos pensar en esto con 2 punteros, pointer1 y pointer2. Empezamos estableciendo ambos punteros en el primer elemento de la lista. Luego recorremos toda la lista con pointer2 e intercambiamos el elemento en la posición de pointer2 si el elemento en la posición pointer2 + 1 es mayor en valor. Seguimos repitiendo este proceso hasta llegar al final de la lista. Luego avanzamos pointer1 en 1 y comenzamos el proceso de nuevo con pointer2.
Quizás hayas notado que necesitamos una forma de evitar revisar elementos que ya hemos ordenado. Dado que el objetivo de cada iteración es mover los elementos más grandes al final de la lista, podemos hacerlo limitando el límite de pointer2 mediante el valor de pointer1 + 1.
¿Cómo lo implementamos?
Aquí hay una implementación muy comentada en Typescript:
function bubbleSort(arr: number[]): void {
// pointer 1
for (let i = 0; i < arr.length; ++i) {
// pointer 2 + limit iterations by pointer1 + 1
for (let j = 0; j < arr.length - 1 - i; ++j) {
// check if current item is larger than the next item
if (arr[j] > arr[j + 1]) {
// temporarily store the current item so we don't lose it
const tmp = arr[j];
// swap the items in the array
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
Ordenado
Este no es un algoritmo al que probablemente se recurra en la mayoría de los casos, pero creo que es uno agradable y fácil para empezar. ¡Espero que te haya resultado útil o, al menos, un poco interesante!