Algoritmo de clasificación de burbujas usando JavaScript

El algoritmo de clasificación de burbujas es un algoritmo que clasifica la array comparando dos elementos adyacentes y los intercambia si no están en el orden previsto. Aquí el orden puede ser cualquier orden creciente o decreciente.

Cómo funciona Bubble-sort

Tenemos una array sin ordenar arr = [ 1, 4, 2, 5, -2, 3 ] la tarea es ordenar la array usando la clasificación de burbujas. 

La ordenación de burbujas compara el elemento del índice 0 y si el índice 0 es mayor que el índice 1, los valores se intercambian y si el índice 0 es menor que el índice 1, entonces no sucede nada.

luego, el primer índice se compara con el segundo índice, luego el segundo índice se compara con el tercero, y así sucesivamente…

veámoslo con un ejemplo, aquí se ilustra brevemente cada paso

Las comparaciones ocurren hasta el último elemento de la array.

Después de cada iteración, el mayor valor de la array se convierte en el último índice de la array. en cada iteración, la comparación ocurre hasta el último elemento sin ordenar.

Ahora la comparación se redujo un paso porque el elemento más grande está en el lugar correcto

Después de todas las iteraciones y comparaciones de elementos, obtenemos una array ordenada.

Sintaxis

BubbleSort(array){
  for i -> 0 to arrayLength 
     for j -> 0 to (arrayLength - i - 1)
      if arr[j] > arr[j + 1]
        swap(arr[j], arr[j + 1])
}

Implementación 

// Bubble sort Implementation using Javascript
 
 
// Creating the bblSort function
 function bblSort(arr){
    
 for(var i = 0; i < arr.length; i++){
    
   // Last i elements are already in place 
   for(var j = 0; j < ( arr.length - i -1 ); j++){
      
     // Checking if the item at present iteration
     // is greater than the next iteration
     if(arr[j] > arr[j+1]){
        
       // If the condition is true then swap them
       var temp = arr[j]
       arr[j] = arr[j + 1]
       arr[j+1] = temp
     }
   }
 }
 // Print the sorted array
 console.log(arr);
}
 
 
// This is our unsorted array
var arr = [234, 43, 55, 63,  5, 6, 235, 547];
 
 
// Now pass this array to the bblSort() function
bblSort(arr);

Output 
Sorted array :
[5, 6, 43, 55, 63, 234, 235, 547]

Nota: Esta implementación no está optimizada. Veremos la solución optimizada a continuación.

Solución optimizada

Como discutimos anteriormente, la implementación de la ordenación de burbuja no está optimizada. Incluso si la array está ordenada, el código se ejecutará con una complejidad O (n ^ 2). Veamos cómo implementar un algoritmo de clasificación de burbujas optimizado en javascript.

La sintaxis para la solución optimizada

BubbleSort(array){
  for i -> 0 to arrayLength 
     isSwapped <- false
     for j -> 0 to (arrayLength - i - 1)
      if arr[j] > arr[j + 1]
        swap(arr[j], arr[j + 1])
        isSwapped -> true
}

Implementación

// Optimized implementation of bubble sort Algorithm
 
function bubbleSort(arr){
   
  var i, j;
  var len = arr.length;
   
  var isSwapped = false;
   
  for(i =0; i < len; i++){
     
    isSwapped = false;
     
    for(j = 0; j < len; j++){
        if(arr[j] > arr[j + 1]){
          var temp = arr[j]
          arr[j] = arr[j+1];
          arr[j+1] = temp;
          isSwapped = true;
        }
    }
     
    // IF no two elements were swapped by inner loop, then break
     
    if(!isSwapped){
      break;
    }
  }
   
  // Print the array
  console.log(arr)
}
 
 
var arr = [243, 45, 23, 356, 3, 5346, 35, 5];
 
// calling the bubbleSort Function
bubbleSort(arr)

Output
Sorted Array :
[3, 5, 23, 35, 45, 243, 356, 5346]

Complejidades

Peor caso y complejidad de tiempo de caso promedio 

Si la array está en orden inverso, esta condición es el peor de los casos y su complejidad temporal es O(n ² ).

Complejidad de tiempo en el mejor de los casos

Si la array ya está ordenada, entonces es el mejor de los casos y su complejidad de tiempo es O (n)

Espacio Auxiliar : O(1)