Tecnología · 3o de Preparatoria · Pensamiento Computacional y Algoritmos Complejos · I Bimestre

Algoritmos de Búsqueda y Ordenamiento

Los estudiantes implementan y comparan algoritmos de búsqueda (lineal, binaria) y ordenamiento (burbuja, selección, inserción, quicksort, mergesort).

• Aprendizajes Esperados SEP
• SEP EMS: Optimización de Procesos Computacionales
• SEP EMS: Algoritmos y Programación

Acerca de este tema

Los algoritmos de búsqueda y ordenamiento son herramientas fundamentales en el pensamiento computacional. En este tema, los estudiantes de 3° de preparatoria implementan y comparan búsqueda lineal y binaria, así como ordenamiento por burbuja, selección, inserción, quicksort y mergesort. La búsqueda lineal recorre elementos secuencialmente, mientras que la binaria requiere datos ordenados y divide el espacio de búsqueda por la mitad en cada paso, lo que demuestra la importancia de la preordenación para la eficiencia.

En el contexto del plan SEP, este contenido fortalece la optimización de procesos computacionales y la programación avanzada. Los estudiantes analizan cómo quicksort y mergesort manejan grandes conjuntos de datos mediante partición y fusión, respondiendo preguntas clave sobre eficiencia según el tamaño de entrada y tipo de datos. Esta comparación fomenta el análisis de complejidad temporal, como O(n²) para burbuja versus O(n log n) para quicksort en promedio.

El aprendizaje activo beneficia este tema porque las simulaciones manuales y codificaciones colaborativas hacen visibles las diferencias en pasos y tiempos de ejecución. Cuando los estudiantes ordenan tarjetas o miden tiempos reales en programas, comprenden intuitivamente por qué ciertos algoritmos escalan mejor, reteniendo conceptos abstractos mediante experiencia práctica.

Preguntas Clave

1. ¿Cómo la pre-ordenación de datos impacta la eficiencia de los algoritmos de búsqueda?
2. ¿De qué manera el algoritmo Quicksort optimiza el tiempo de ordenamiento en grandes conjuntos de datos?
3. ¿Por qué algunos algoritmos de ordenamiento son más adecuados para ciertos tipos de datos o tamaños de entrada?

Objetivos de Aprendizaje

• Comparar la eficiencia temporal de los algoritmos de búsqueda lineal y binaria para diferentes tamaños de conjuntos de datos.
• Analizar la complejidad de tiempo (O(n^2) vs O(n log n)) de los algoritmos de ordenamiento burbuja, selección, inserción, quicksort y mergesort.
• Implementar en código los algoritmos de búsqueda binaria y ordenamiento por selección.
• Evaluar qué algoritmo de ordenamiento es más adecuado para ordenar listas pequeñas versus listas grandes, justificando la elección.
• Explicar cómo la pre-ordenación de datos afecta significativamente la velocidad de los algoritmos de búsqueda.

Antes de Empezar

Introducción a los Algoritmos y Secuencias de Instrucciones

Por qué: Los estudiantes deben comprender qué es un algoritmo y cómo seguir una secuencia de pasos para poder implementar y analizar algoritmos más complejos.

Estructuras de Datos Básicas (Listas/Arreglos)

Por qué: Es fundamental que los estudiantes manejen conceptos de listas o arreglos para poder aplicarles algoritmos de búsqueda y ordenamiento.

Vocabulario Clave

Búsqueda Lineal	Algoritmo que revisa cada elemento de una lista uno por uno hasta encontrar el valor buscado o agotar la lista.
Búsqueda Binaria	Algoritmo que busca eficientemente un elemento en una lista ordenada, dividiendo repetidamente a la mitad el intervalo de búsqueda.
Algoritmo de Ordenamiento Burbuja	Método simple que compara pares de elementos adyacentes y los intercambia si están en el orden incorrecto, repitiendo hasta que la lista esté ordenada.
Algoritmo Quicksort	Algoritmo de ordenamiento eficiente que utiliza la técnica de 'divide y vencerás', seleccionando un elemento 'pivote' y particionando la lista alrededor de él.
Complejidad Temporal	Medida que describe cuánto tiempo tarda un algoritmo en ejecutarse en función del tamaño de la entrada, a menudo expresada en notación Big O.

Cuidado con estas ideas erróneas

Idea errónea común

La búsqueda binaria funciona igual en listas desordenadas que ordenadas.

Qué enseñar en su lugar

La binaria requiere orden previo, ya que asume partición equilibrada. Actividades de simulación manual ayudan, pues estudiantes ven fallos inmediatos al omitir ordenamiento y corrigen comparando con lineal en discusiones grupales.

Idea errónea común

Todos los algoritmos de ordenamiento tienen la misma velocidad.

Qué enseñar en su lugar

Eficiencia varía: burbuja es O(n²), quicksort O(n log n) promedio. Pruebas cronometradas en parejas revelan esto, fomentando debates donde ajustan percepciones con datos reales.

Idea errónea común

Quicksort es siempre el más rápido.

Qué enseñar en su lugar

En listas ordenadas casi, degrada a O(n²); mergesort es estable. Comparaciones clase-wide con datasets variados muestran trade-offs, ayudando a elegir por contexto mediante gráficos colaborativos.

Ideas de aprendizaje activo

Simulación Manual: Ordenamiento Burbuja vs. Selección

Entrega a cada grupo mazos de 20 tarjetas con números. Un subgrupo simula burbuja intercambiando adyacentes, otro selección buscando mínimos. Comparan conteo de intercambios y tiempo transcurrido, registrando en tabla. Discuten eficiencia al duplicar tarjetas.

30 min·Grupos pequeños

Codificación en Parejas: Búsqueda Binaria

Parejas escriben código para búsqueda binaria en listas ordenadas de 100 elementos. Prueban con datos generados aleatoriamente, miden comparaciones con cronómetro. Intercambian códigos para probar en listas no ordenadas y corrigen errores.

45 min·Parejas

Comparación de Tiempos: Quicksort vs. Mergesort

Clase genera datasets crecientes (100, 1000 elementos) en Python. Implementan ambos algoritmos y ejecutan 10 veces cada uno, promediando tiempos. Grafican resultados en Google Sheets para visualizar complejidad.

50 min·Toda la clase

Torneo de Algoritmos: Elección Individual

Cada estudiante elige un algoritmo, lo implementa y lo prueba contra datasets públicos. Registra tiempos y envía a foro clase. Votan por el más eficiente según escenarios dados.

25 min·Individual

Conexiones con el Mundo Real

• Los bibliotecarios utilizan algoritmos de ordenamiento (como el de inserción o el de burbuja para listas pequeñas) para organizar físicamente los libros en los estantes por autor o título, facilitando su localización.
• Los ingenieros de software que desarrollan motores de búsqueda como Google emplean algoritmos de ordenamiento y búsqueda muy eficientes (similares a Quicksort o Mergesort) para indexar y recuperar miles de millones de páginas web en fracciones de segundo.
• Los analistas financieros utilizan algoritmos de ordenamiento para clasificar grandes volúmenes de datos bursátiles, identificando tendencias o valores atípicos de manera rápida y precisa.

Ideas de Evaluación

Boleto de Salida

Entregue a cada estudiante una tarjeta con el nombre de un algoritmo (ej. Búsqueda Binaria, Ordenamiento Burbuja). Pida que escriban una oración explicando cuándo sería una buena opción usarlo y una oración explicando cuándo sería una mala opción.

Verificación Rápida

Presente una lista pequeña de 5 números desordenados. Pida a los estudiantes que demuestren manualmente los primeros dos pasos del algoritmo de ordenamiento por selección. Revise la corrección de los intercambios realizados.

Pregunta para Discusión

Plantee la pregunta: 'Si tuvieras que ordenar una lista de 1000 nombres de estudiantes para una lista de asistencia, ¿qué algoritmo de ordenamiento elegirías y por qué? ¿Cómo se compara tu elección con el ordenamiento burbuja?'

Preguntas frecuentes

¿Cómo impacta la preordenación en la eficiencia de búsqueda?

La preordenación permite búsqueda binaria, reduciendo comparaciones de O(n) a O(log n). Sin ella, solo lineal aplica. Estudiantes lo ven implementando ambos en código y midiendo tiempos con listas grandes, entendiendo por qué bases de datos reales ordenan primero.

¿Por qué quicksort optimiza ordenamiento en grandes datos?

Usa pivote para particionar recursivamente, logrando O(n log n) promedio. Divide y conquista minimiza trabajo. Simulaciones manuales con tarjetas muestran cómo balancea sublistas, mientras ejecuciones programadas confirman escalabilidad en datasets reales de miles de elementos.

¿Cuándo usar burbuja versus mergesort?

Burbuja para datos pequeños o educativos por simplicidad, pese a O(n²). Mergesort para grandes volúmenes o estabilidad, con O(n log n) garantizado. Actividades comparativas ayudan elegir: pruebas muestran burbuja lenta en n>50, ideal para discutir contextos.

¿Cómo el aprendizaje activo ayuda en algoritmos de búsqueda y ordenamiento?

Simulaciones físicas como ordenar cartas hacen abstracto concreto, contando pasos reales. Codificación colaborativa y cronometrajes revelan complejidades ocultas. Discusiones post-actividad conectan observaciones a notación Big O, mejorando retención 30-50% según estudios, versus solo teoría.