Resumen de Algoritmos

Los diez algoritmos de ordenamiento comunes se dividen en dos categorías principales:

• Ordenamiento por comparación: decide el orden relativo de los elementos mediante comparaciones. Su complejidad temporal no puede superar O(n log n), por lo que también se denomina ordenamiento por comparación no lineal.
• Ordenamiento no comparativo: no utiliza comparaciones para determinar el orden relativo; puede superar el límite inferior de tiempo de los algoritmos basados en comparación y se ejecuta en tiempo lineal, por lo que también se llama ordenamiento lineal no comparativo.

Complejidad de los Algoritmos

Complejidad de los algoritmos

Método de ordenamiento	Complejidad temporal (promedio)	Complejidad temporal (peor caso)	Complejidad temporal (mejor caso)	Complejidad espacial	Estabilidad
Ordenamiento por inserción	O(n²)	O(n²)	O(n)	O(1)	Estable
Ordenamiento Shell	O(n¹·³)	O(n²)	O(n)	O(1)	Inestable
Ordenamiento por selección	O(n²)	O(n²)	O(n²)	O(1)	Inestable
Ordenamiento por montón	O(n log₂ n)	O(n log₂ n)	O(n log₂ n)	O(1)	Inestable
Ordenamiento burbuja	O(n²)	O(n²)	O(n)	O(1)	Estable
Ordenamiento rápido	O(n log₂ n)	O(n²)	O(n log₂ n)	O(n log₂ n)	Inestable
Ordenamiento por mezcla	O(n log₂ n)	O(n log₂ n)	O(n log₂ n)	O(n)	Estable
Ordenamiento por conteo	O(n + k)	O(n + k)	O(n + k)	O(n + k)	Estable
Ordenamiento por cubos	O(n + k)	O(n²)	O(n)	O(n + k)	Estable
Ordenamiento radix	O(n·k)	O(n·k)	O(n·k)	O(n + k)	Estable

Conceptos Relacionados

• Estable: Si a está originalmente antes que b y a = b, después del ordenamiento a sigue antes que b.
• Inestable: Si a está originalmente antes que b y a = b, después del ordenamiento a puede aparecer después de b.
• Complejidad temporal: Número total de operaciones realizadas sobre los datos. Refleja cómo crece el número de operaciones cuando n cambia.
• Complejidad espacial: Medida del espacio de almacenamiento requerido por el algoritmo durante la ejecución; también es una función del tamaño de datos n.

Selección del Algoritmo

• Si n es pequeño (n ≤ 50), se puede usar ordenamiento por inserción directa o selección directa.
• Si el archivo inicial está básicamnete ordenado (en orden ascendente), es adecuado usar inserción directa, burbuja o un ordenamiento rápido aleatorio.
• Si n es grande, se deben usar métodos con complejidad O(n log n): ordenamiento rápido, montón o mezcla.
• Si n es pequeño y se requiere estabilidad, se puede usar ordenamiento radix, conteo o cubos.

El ordenamiento por inserción y mezcla son amigables con datos de alta repetición; el burbuja no es adecuado para grandes volúmenes.

1. Ordenamiento Burbuja

---

Concepto: Algoritmo simple que recorre repetidamente la lista, compara elementos adyacentes y los intercambia si están en el orden incorrecto. El proceso se repite hasta que no se necesiten más intercambios. Los elementos más pequeños "flotan" hacia la cima.

Descripción del algoritmo:

• Comparar elementos adyacentes. Si el primero es mayor que el segundo, intercambiarlos.
• Repetir para cada par de elementos adyacentes, desde el primero hasta el último. Al final, el elemento más grande estará al final.
• Repetir los pasos anteriores para todos los elementos excepto el último.
• Repetir hasta que la lista esté ordenada.

Animación:

Ejemplo de código:

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

const datos = [6, 5, 4, 3, 2, 1];
console.log('Original:', datos);
bubbleSort(datos);
console.log('Ordenado:', datos); // [1, 2, 3, 4, 5, 6]

2. Ordenamiento por Selección

---

Concepto: Busca el elemento más pequeño (o más grande) en la parte no ordenada y lo coloca al inicio. Repite hasta ordenar todo. Es estable en complejidad O(n²) y no requiere memoria extra.

Descripción:

• Estado inicial: la zona desordenada es R[1..n], la zona ordenada está vacía.
• En la i-ésima iteración (i de 1 a n-1), se encuentra el elemento mínimo en la zona desordenada y se intercambia con el primer elemento de dicha zona.
• Después de n-1 iteraciones, el array queda ordenado.

Animación:

Ejemplo:

function selectionSort(arr) {
  if (arr.length < 2) return arr;
  for (let i = 0; i < arr.length - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIdx]) minIdx = j;
    }
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }
  return arr;
}

const datos = [1, 3, 2, 8, 9, 1, 5];
console.log('Original:', datos);
selectionSort(datos);
console.log('Ordenado:', datos); // [1, 1, 2, 3, 5, 8, 9]

3. Ordenamiento por Inserción

---

Concepto: Construye una secuencia ordenada tomando elementos no ordenados y colocándolos en la posición correcta desplazando los elementos mayores hacia la derecha. Utiliza espacio adicional O(1).

Descripción:

• El primer elemento se considera ya ordenado.
• Tomar el siguiente elemento y escanear hacia atrás en la secuencia ordenada.
• Si el elemento ordenado es mayor que el nuevo, desplazarlo una posición a la derecha.
• Repetir hasta encontrar una posición donde el elemento ordenado sea menor o igual al nuevo.
• Insertar el nuevo elemento en esa posición.
• Repetir hasta ordenar todos.

Animación:

Ejemplo:

function insertionSort(arr) {
  if (arr.length < 2) return arr;
  for (let i = 1; i < arr.length; i++) {
    let j = i - 1;
    while (j >= 0 && arr[j] > arr[j + 1]) {
      [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      j--;
    }
  }
  return arr;
}

const datos = [3, 4, 2, 1, 6, 7, 8, 4];
console.log('Original:', datos);
insertionSort(datos);
console.log('Ordenado:', datos); // [1, 2, 3, 4, 4, 6, 7, 8]

4. Ordenamiento Shell

---

Concepto: Mejora del ordenamiento por inserción que compara elementos distantes. También llamado "ordenamiento por incremento decreciente". La elección de la secuencia de espacios es clave.

Descripción:

• Elegir una secuencia de espacios t1, t2, ..., tk, donde ti > tj y tk = 1.
• Realizar k pasadas según la secuencia.
• En cada pasada, con espacio ti, dividir la lista en sublistas de longitud m y aplicar inserción directa. Cuando el espacio es 1, se trata la lista completa.

Animación:

Ejemplo:

function shellSort(arr) {
  const n = arr.length;
  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < n; i++) {
      for (let j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap) {
        [arr[j], arr[j + gap]] = [arr[j + gap], arr[j]];
      }
    }
  }
  return arr;
}

const datos = [49, 38, 65, 97, 76, 13, 27, 49, 55, 4];
console.log('Original:', datos);
shellSort(datos);
console.log('Ordenado:', datos); // [4, 13, 27, 38, 49, 49, 55, 65, 76, 97]

5. Ordenamiento por Mezcla

---

Concepto: Aplica la técnica de divide y vencerás. Divide la secuencia en subsecuencias más pequeñas, las ordena y luego las fusiona. Es estable y tiene complejidad O(n log n) pero requiere espacio adicional O(n).

Descripción:

• Dividir la secuencia de longitud n en dos subsecuencias de longitud n/2.
• Aplicar ordenamiento por mezcla recursivamente a cada subsecuencia.
• Fusionar las dos subsecuencias ordenadas en una sola secuencia ordenada.

Animación:

Ejemplo:

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

const datos = [6, 4, 2, 1, 12, 4, 6, 5, 5, 0];
console.log('Original:', datos);
const ordenado = mergeSort(datos);
console.log('Ordenado:', ordenado); // [0, 1, 2, 4, 4, 5, 5, 6, 6, 12]

6. Ordenamiento Rápido

---

Concepto: Selecciona un pivote y particiona la lista de modo que los elementos menores queden a la izquierda y los mayores a la derecha. Luego ordena recursivamente las particiones. Es inestable.

Descripción:

• Escoger un elemento como pivote (por ejemplo, el último).
• Reordenar la lista: los menores que el pivote a la izquierda, los mayores a la derecha. El pivote queda en su posición final.
• Aplicar recursivamente a las sublistas izquierda y derecha.

Animación:

Ejemplo:

function quickSort(arr) {
  if (arr.length < 2) return arr;
  const pivote = arr[arr.length - 1];
  const izquierda = [];
  const derecha = [];
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivote) {
      izquierda.push(arr[i]);
    } else {
      derecha.push(arr[i]);
    }
  }
  return [...quickSort(izquierda), pivote, ...quickSort(derecha)];
}

// Versión in-place más eficiente
function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return;
  let i = left, j = right;
  const pivote = arr[j];
  while (i < j) {
    while (i < j && arr[i] <= pivote) i++;
    arr[j] = arr[i];
    while (j > i && arr[j] >= pivote) j--;
    arr[i] = arr[j];
  }
  arr[j] = pivote;
  quickSortInPlace(arr, left, j - 1);
  quickSortInPlace(arr, j + 1, right);
  return arr;
}

const datos = [6, 5, 4, 5, 3, 4, 1];
console.log('Original:', datos);
console.log('Ordenado:', quickSort(datos.slice())); // [1, 3, 4, 4, 5, 5, 6]

7. Ordenamiento por Montón

---

Concepto: Utiliza una estructura de heap (montículo) binario. Construye un max-heap, intercambia la raíz (máximo) con el último elemento, reduce el tamaño del heap y reajusta. Repite hasta ordenar.

Descripción:

• Construir un max-heap con la secuencia inicial (zona desordenada).
• Intercambiar la raíz (R[1]) con el último elemento (R[n]). Ahora el heap es más pequeño.
• Reajustar el heap con los elementos restantes.
• Repetir hasta que solo quede un elemento.

Animación:

Ejemplo:

function heapSort(arr) {
  const n = arr.length;

  function heapify(i, size) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    if (left < size && arr[left] > arr[largest]) largest = left;
    if (right < size && arr[right] > arr[largest]) largest = right;
    if (largest !== i) {
      [arr[i], arr[largest]] = [arr[largest], arr[i]];
      heapify(largest, size);
    }
  }

  // Construir max-heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(i, n);
  }

  // Extraer elementos uno por uno
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(0, i);
  }
  return arr;
}

const datos = [2, 6, 5, 3, 8, 4, 10, 23];
console.log('Original:', datos);
heapSort(datos);
console.log('Ordenado:', datos); // [2, 3, 4, 5, 6, 8, 10, 23]

8. Ordenamiento por Conteo

---

Concepto: Algoritmo no comparativo que cuenta las ocurrencias de cada valor. Requiere que los datos sean enteros en un rango conocido. Complejidad O(n + k) estable.

Descripción:

• Encontrar el valor máximo y mínimo del array.
• Crear un array de conteo C con tamaño (max - min + 1) inicializado a cero.
• Contar las ocurrencias de cada valor.
• Acumular los conteos (opcional para orden estable).
• Colocar los elementos en el array de salida según el conteo.

Animación:

Ejemplo:

function countingSort(arr, maxVal) {
  const count = new Array(maxVal + 1).fill(0);
  const output = [];

  for (let num of arr) {
    count[num]++;
  }

  for (let i = 0; i <= maxVal; i++) {
    while (count[i] > 0) {
      output.push(i);
      count[i]--;
    }
  }
  return output;
}

const datos = [4, 3, 3, 2, 3, 4, 5, 6, 3, 5, 6, 4, 6, 5, 2, 1, 2];
console.log('Original:', datos);
const ordenado = countingSort(datos, 6);
console.log('Ordenado:', ordenado); // [1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6]

9. Ordenamiento por Cubos

---

Concepto: Mejora del conteo. Distribuye los datos en un número fijo de cubos (buckets) según una función de mapeo, luego ordena cada cubo individualmente (por ejemplo con inserción) y concatena los resultados. Es estable si el orden interno es estable.

Descripción:

• Crear un array de cubos vacíos.
• Recorrer los datos y colocar cada elemento en el cubo correspondiente (mapeo).
• Ordenar cada cubo no vacío.
• Concatenar los cubos ordenados.

Animación:

Ejemplo:

function bucketSort(arr, bucketSize = 5) {
  if (arr.length === 0) return arr;

  let min = arr[0], max = arr[0];
  for (let num of arr) {
    if (num < min) min = num;
    if (num > max) max = num;
  }

  const bucketCount = Math.floor((max - min) / bucketSize) + 1;
  const buckets = Array.from({ length: bucketCount }, () => []);

  for (let num of arr) {
    const idx = Math.floor((num - min) / bucketSize);
    buckets[idx].push(num);
  }

  arr.length = 0;
  for (let bucket of buckets) {
    insertionSort(bucket); // reutilizamos la función de inserción
    for (let val of bucket) {
      arr.push(val);
    }
  }
  return arr;
}

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let j = i - 1;
    while (j >= 0 && arr[j] > arr[j + 1]) {
      [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      j--;
    }
  }
  return arr;
}

const datos = [8, 39, 400, 500, 3, 4, 20, 44, 440];
console.log('Original:', datos);
bucketSort(datos, 10);
console.log('Ordenado:', datos); // [3, 4, 8, 20, 39, 44, 400, 440, 500]

10. Ordenamiento Radix

---

Concepto: Ordena los dígitos desde la posición menos significativa hasta la más significativa. Usa un ordenamiento estable (como conteo) en cada paso. Complejidad O(d·n), donde d es el número de dígitos.

Descripción:

• Encontrar el número máximo y determinar su cantidad de dígitos.
• Para cada dígito (de manor a mayor):
  • Usar un ordenamiento por conteo estable para agrupar los números por el dígito actual.
  • Reconstruir el array.

Animación:

Ejemplo:

function radixSort(arr, maxDigits) {
  for (let pos = 0; pos < maxDigits; pos++) {
    const buckets = Array.from({ length: 10 }, () => []);
    const divisor = Math.pow(10, pos);
    for (let num of arr) {
      const digit = Math.floor(num / divisor) % 10;
      buckets[digit].push(num);
    }
    arr.length = 0;
    for (let bucket of buckets) {
      arr.push(...bucket);
    }
  }
  return arr;
}

const datos = [4, 5, 3, 1, 7, 4, 3, 2, 0, 4, 3];
console.log('Original:', datos);
radixSort(datos, 2); // máximo 7, 2 dígitos son suficientes
console.log('Ordenado:', datos); // [0, 1, 2, 3, 3, 3, 4, 4, 4, 5, 7]