¿Qué es Shell Sort?

Shell Sort es un algoritmo de ordenamiento basado en el enfoque de inserción, pero que mejora su eficiencia al permitir intercambios de elementos lejanos. Divide el arreglo en segmentos (determinados por un valor llamado "gap") y realiza múltiples pasadas de ordenamiento por inserción con valores decrecientes de gap.

El Código

                
function shellSort(arr) {
  let n = arr.length;
  let gap = Math.floor(n / 2);

  while (gap > 0) {
    for (let i = gap; i < n; i++) {
      let temp = arr[i];
      let j;
      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
        arr[j] = arr[j - gap];
      }
      arr[j] = temp;
    }
    gap = Math.floor(gap / 2);
  }

  return arr;
}

// Ejemplo de uso
const array = [12, 34, 54, 2, 3];
console.log("Array ordenado:", shellSort(array));
                
            

Puntos Clave del Algoritmo

• Entrada: Un arreglo desordenado (arr).
• Salida: El arreglo ordenado de menor a mayor.
• Método:
  • Define un valor inicial para el gap (normalmente la mitad del tamaño del arreglo).
  • Realiza un ordenamiento por inserción dentro de los segmentos separados por el gap.
  • Reduce el gap en cada iteración hasta que sea 1, momento en el cual se realiza una última pasada de inserción estándar.
• Complejidad:
  • Peor caso: Depende de la secuencia de gap utilizada, pero generalmente es O(n²).
  • Promedio: Entre O(n log² n) y O(n¹.⁵), dependiendo de la implementación.
• Ventajas: Es más eficiente que la inserción directa para arreglos grandes y permite intercambios lejanos.
• Desventajas: Su rendimiento depende fuertemente de la elección de la secuencia de gap.

Ejemplo de Ejecución

Arreglo inicial: [12, 34, 54, 2, 3]

Proceso de ordenamiento:

1. Gap = 2: Se comparan y ordenan elementos separados por dos posiciones: [12, 34, 54, 2, 3] → [12, 3, 54, 2, 34].
2. Gap = 1: Ordenamiento por inserción estándar: [12, 3, 54, 2, 34] → [3, 12, 2, 34, 54] → [3, 2, 12, 34, 54].

Resultado final: [2, 3, 12, 34, 54]

Información Adicional

Shell Sort es una mejora directa del ordenamiento por inserción y es eficiente para arreglos de tamaño moderado. Aunque no es el más rápido, su simplicidad y bajo requerimiento de memoria lo hacen útil en sistemas con limitaciones.