¿Qué es Insertion Sort?

El algoritmo Insertion Sort (ordenamiento por inserción) organiza un arreglo construyendo un subarreglo ordenado uno por uno. Para cada elemento, lo inserta en la posición correcta dentro del subarreglo ya ordenado.

El Código

                
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
  return arr;
}

// Ejemplo de uso
const array = [34, 7, 23, 32, 5, 62];
console.log("Array ordenado:", insertionSort(array));
                
            

Puntos Clave del Algoritmo

• Entrada: Un arreglo desordenado (arr).
• Salida: El arreglo ordenado de menor a mayor.
• Método:
  • Recorre el arreglo desde el segundo elemento.
  • Compara el elemento actual (key) con los elementos anteriores del subarreglo ordenado.
  • Mueve los elementos mayores hacia la derecha para hacer espacio e inserta el elemento en la posición correcta.
• Complejidad:
  • Peor caso: O(n²), ocurre cuando el arreglo está en orden inverso.
  • Mejor caso: O(n), ocurre cuando el arreglo ya está ordenado.
• Ventajas: Es simple, estable y eficiente para arreglos pequeños.
• Desventajas: Ineficiente para arreglos grandes en comparación con algoritmos como Quick Sort o Merge Sort.

Ejemplo de Ejecución

Arreglo inicial: [34, 7, 23, 32, 5, 62]

Proceso de ordenamiento:

1. Iteración 1: Inserta 7 antes de 34. Resultado: [7, 34, 23, 32, 5, 62]
2. Iteración 2: Inserta 23 entre 7 y 34. Resultado: [7, 23, 34, 32, 5, 62]
3. Iteración 3: Inserta 32 entre 23 y 34. Resultado: [7, 23, 32, 34, 5, 62]
4. Iteración 4: Inserta 5 al inicio. Resultado: [5, 7, 23, 32, 34, 62]
5. Iteración 5: No hay cambio, 62 ya está en su posición. Resultado final: [5, 7, 23, 32, 34, 62]

Arreglo final ordenado: [5, 7, 23, 32, 34, 62]

Información Adicional

Insertion Sort es un algoritmo útil cuando se trabaja con pequeños conjuntos de datos o cuando los datos están casi ordenados. Su estabilidad lo hace ideal para aplicaciones en las que el orden relativo de los elementos iguales es importante.