Algoritmos estándar: búsqueda y ordenamiento – Búsqueda lineal/binaria, BubbleSort, SelectionSort e InsertionSort

Este artículo es una guía de conceptos sobre algoritmos de búsqueda y ordenamiento, incluyendo preguntas de examen y referencias.

En pocas palabras

Estos algoritmos estándar sirven para localizar datos rápidamente (búsqueda) u organizarlos en orden (ordenamiento) dentro de arrays o listas. Forman la base fundamental para desarrollar pensamiento algorítmico, un tema común en exámenes.

Descripción técnica compacta

La búsqueda lineal y binaria son procedimientos elementales para encontrar un valor en estructuras de datos. La búsqueda lineal examina cada elemento de forma secuencial, mientras que la búsqueda binaria aprovecha una lista ordenada y divide el espacio de búsqueda a la mitad. Los algoritmos de ordenamiento como Bubble Sort, Selection Sort e Insertion Sort organizan datos en secuencia. Bubble Sort compara elementos adyacentes repetidamente, Selection Sort encuentra el elemento más pequeño e intercambia posiciones, e Insertion Sort construye gradualmente una lista ordenada. Estos algoritmos se diferencian principalmente en complejidad y eficiencia (Big-O).

Puntos clave para el examen

• Búsqueda lineal examina cada elemento secuencialmente (O(n))
• Búsqueda binaria divide iterativamente el rango de búsqueda (O(log n), solo en datos ordenados)
• Bubble Sort compara e intercambia elementos adyacentes múltiples veces (O(n²))
• Selection Sort busca el mínimo en cada iteración e intercambia hacia el inicio (O(n²))
• Insertion Sort ordena insertando sucesivamente elementos (O(n²), pero eficiente con datos casi ordenados)
• Comprender la lógica de ejecución es crítico para el examen (pseudocódigo, dry run)
• Estabilidad, uso de memoria y complejidad varían significativamente

Componentes principales

1. Búsqueda lineal
2. Búsqueda binaria
3. Bubble Sort
4. Selection Sort
5. Insertion Sort
6. Complejidad de tiempo (Big-O)
7. Estabilidad (preservación del orden de elementos iguales)
8. Ejecución iterativa con gestión de índices
9. Validación contra errores de índice
10. Dry run para verificación

Ejemplo práctico

// Ejemplo: Insertion Sort
función insertionSort(array)
para i desde 1 hasta array.longitud - 1
    clave = array[i]
    j = i - 1
    mientras j >= 0 y array[j] > clave
        array[j + 1] = array[j]
        j = j - 1
    array[j + 1] = clave

Explicación: El elemento actual se inserta en la posición correcta dentro de la parte izquierda ya ordenada.

Ventajas y desventajas

Ventajas

• Fáciles de implementar y entender
• Ideales para conjuntos de datos pequeños o casi ordenados
• Estables (especialmente Insertion Sort)

Desventajas

• Ineficientes con grandes volúmenes de datos (O(n²))
• Bubble Sort y Selection Sort requieren muchas comparaciones
• Búsqueda binaria solo funciona en arrays ordenados

Preguntas típicas de examen (con respuesta breve)

1. ¿Cómo funciona la búsqueda binaria y cuándo se aplica? Divide iterativamente el rango de búsqueda, solo aplicable en datos ordenados.
2. ¿Diferencia entre Bubble Sort y Selection Sort? Bubble Sort compara vecinos, Selection Sort busca el mínimo en cada pasada.
3. ¿Por qué Insertion Sort es estable? Los elementos iguales conservan su orden original.
4. ¿Tiempo de ejecución de Bubble Sort en el peor caso? O(n²), porque cada elemento se compara múltiples veces.
5. ¿Qué significa estabilidad en algoritmos de ordenamiento? Los elementos iguales preservan su orden relativo.
6. ¿Búsqueda más eficiente en datos ordenados? Búsqueda binaria con O(log n).
7. ¿Por qué Insertion Sort es eficiente con datos casi ordenados? Porque requiere pocas comparaciones e inserciones.
8. ¿Cómo verificar un algoritmo con dry run? Ejecutando manualmente los pasos intermedios con datos concretos.

Recursos principales

1. https://visualgo.net/en/sorting
2. https://www.geeksforgeeks.org/sorting-algorithms
3. https://cs-field-guide.org.nz/en/chapters/algorithms