Concepto

El ordenamiento burbuja es un algoritmo de clasificación que opera mediante la comparación iterativa de elementos adyacentes, intercambiándolos cuando no se encuentran en el orden deseado para organiazr la secuencia completa.

Características

Análisis de Complejidad

• Tiempo: Mejor caso O(n), peor caso O(n^2), caso promedio O(n^2)
• Espacio: O(1), ya que se ejecuta en su lugar sin requerir memoria adicionnal significativa

Escenarios de Aplicación

Debido a su complejidad temporal de O(n^2), este algoritmo es más eficiente para conjuntos de datos reducidos y no se recomienda para grandes volúmenes de información.

Implementación en Código

A continuación se muestra la implementación del algoritmo en TypeScript:

import { probarAlgoritmo } from './utilidades';

/**
 * @desc : Implementación del algoritmo de ordenamiento burbuja
 */
function burbujaOrdenar(elementos: number[]): number[] {
  const cantidad = elementos.length;

  for (let iteracion = 0; iteracion < cantidad; iteracion++) {
    let intercambioRealizado = false;

    for (let posicion = 0; posicion < cantidad - 1 - iteracion; posicion++) {
      if (elementos[posicion] > elementos[posicion + 1]) {
        // Realizar intercambio de elementos
        [elementos[posicion], elementos[posicion + 1]] = [elementos[posicion + 1], elementos[posicion]];
        intercambioRealizado = true;
      }
    }

    if (!intercambioRealizado) break;
  }

  return elementos;
}

// Ejecutar prueba del algoritmo
probarAlgoritmo(burbujaOrdenar);

// Ejemplo de uso
let conjunto = [10, 90, 20, 100, 50];
console.log('Estado inicial:', conjunto); // [10, 90, 20, 100, 50]

let resultado = burbujaOrdenar(conjunto);
console.log('Estado final:', resultado); // [10, 20, 50, 90, 100]

Función de utilidad para verificación de orden:

/**
 * @desc : Verifica si un arreglo está ordenado ascendente
 * @param  {number} secuencia: arreglo a evaluar
 * @return {boolean} verdadero si está ordenado, falso en caso contrario
 */
function verificarOrden(secuencia: number[]): boolean {
  for (let indice = 0; indice < secuencia.length - 1; indice++) {
    if (secuencia[indice] > secuencia[indice + 1]) {
      return false;
    }
  }
  return true;
}

/**
 * @desc : Prueba una función de ordenamiento con datos aleatorios
 * @param  {any} funcionOrdenar: función que implementa el algoritmo
 */
export function probarAlgoritmo(funcionOrdenar: Function) {
  // Crear datos de prueba aleatorios
  let datosPrueba = new Array(10);
  for (let i = 0; i < datosPrueba.length; i++) {
    datosPrueba[i] = Math.floor(Math.random() * 500);
  }

  console.log('Datos originales:', datosPrueba);

  let datosProcesados = funcionOrdenar(datosPrueba);
  console.log('Datos procesados:', datosProcesados);

  console.log('Orden correcto:', verificarOrden(datosProcesados));
}