marzo 29, 2024

BitCuco

¡Hola Mundo!

Algoritmo de ordenamiento en Javascript: BubbleSort

En éste tutorial vamos a hablar sobre uno de los más famosos algoritmos de ordenamiento: el algoritmo de ordenamiento burbuja (o bubblesort en inglés), método para ordenar una lista de elementos, que en propósitos generales, para ordenar un array de elementos comparables, mostrando al final su código en Javascript.

Éste algoritmo consiste en ordenar cada par de elementos de la lista al recorrerla ésta en forma repetida, en donde el uso más común es comparar dos elementos y pasar el mayor a la derecha, repitiendo el mismo procedimiento cuantas veces sea necesario, es decir hasta que la lista esté ordenada.

Complejidad del algoritmo

Para el peor caso, en donde cada uno de los elementos es necesario intercambiarlo, sucede en el caso de una lista invertida. Si ordenamos la lista utlizando bubblesort, recorremos la lista de tamaño n, un total de n-1 veces que ordena + 1 vez que no ordena. Es decir n veces n, por lo tanto su complejidad es:

{\displaystyle O(c(n))=O(i(n))=n^{2}\;}

Sin embargo en el caso de tener un arreglo ya ordenado, la complejidad se reduce a recorrer la lista, es decir n.

Ejemplo de uso

Primer iteración: Tomamos un arreglo desordenado y comenzamos a iterar por pares:
( 6 2 5 3 9 ) –> ( 2 6 5 3 9 ), Cambiamos, ya que 6 > 2
( 2 6 5 3 9 ) –>  ( 2 5 6 3 9 ), Cambiamos, ya que 6 > 5
( 2 5 6 3 9 ) –>  ( 2 5 3 6 9 ), Cambiamos, ya que 6 > 3
( 2 5 3 6 9 ) –> ( 2 5 3 6 9 ), Como 9 > 6, está en orden y no cambiamos.

Segunda Iteración:
( 2 5 3 6 9 ) –> ( 2 5 3 6 9 )
( 2 5 3 6 9 ) –> ( 2 3 5 6 9 ), Cambiamos, ya que 5 > 3
( 2 3 5 6 9 ) –> ( 2 3 5 6 9 )
( 2 3 5 6 9 ) –>  ( 2 3 5 6 9 )

Tercera iteración:
( 2 3 5 6 9 ) –> ( 2 3 5 6 9 )
( 2 3 5 6 9 ) –> ( 2 3 5 6 9 )
( 2 3 5 6 9 ) –> ( 2 3 5 6 9 )
( 2 3 5 6 9 ) –> ( 2 3 5 6 9 )

Al no existir más cambios en la última iteración, el algoritmo concluye, debido a que la lista ya está ordenada.

Implementación de BubbleSort en Javascript

Finalmente, mostramos la forma de implementar el algoritmo de ordenamiento bubblesort en el lenguaje de programación Javascript, sin embargo el código es fácilmente acoplable a otros lenguajes de programación, ya que la lógica sigue siendo la misma. Recordamos que está implementado para utilizar un array de elementos comparables, los cuáles pueden ser enteros, flotantes, cadenas (strings) o cualquier tipo de dato que pueda ser comparado (y del mismo tipo).

const bubbleSort = function(array) {             
  let swaps;       
  do {       
    swaps = false;       
    for (let i = 0; i < array.length - 1; i++) {          
      if (array[i] > array[i + 1]) {                       
        let temp = array[i + 1];                    
        array[i + 1] = array[i];       
        array[i] = temp;      
        swaps = true;      
      }       
    }       
  } while (swaps);        
  return array;    
};

Otros problemas interesantes

Te invitamos a conocer otros problemas computacionales interesantes:

Problema del salto del caballo

Crear un JSON

Herencia de clases en Javascript