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 en algo es enseñarlo, y como ya he cumplido mi cuota de aburrir a mi pareja con charlas de programación por el mes (probablemente por 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 típicamente donde se favorece la simplicidad sobre la eficiencia. Tiene una complejidad temporal de O(n^2), lo cual es menos que ideal cuando se trata de listas más grandes.
¿Cómo funciona?
Para explicar cómo funciona, aquí hay algo de 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 hacia 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 movemos pointer1 hacia arriba en 1 y comenzamos el proceso de nuevo con pointer2.
Es posible que 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 hacer esto limitando el límite de pointer2 por el valor de pointer1 + 1.
¿Cómo lo implementamos?
Aquí hay una implementación con muchos comentarios 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 se suela recurrir en la mayoría de los casos, pero creo que es agradable y fácil para empezar. ¡Espero que te haya resultado útil o, al menos, un poco interesante!