Algoritmos cotidianos, de búsqueda y de ordenamiento
Valentina quiere encontrar su nombre en la lista de asistencia del liceo. Mateo, en cambio, quiere dejar la lista de la clase en orden alfabético. Las dos cosas se resuelven con una receta clara, paso a paso, que cualquiera puede seguir sin pensar. En esta página vas a aprender a escribir y a seguir esas recetas, y al final vas a poder decir cuál conviene usar en cada caso.
Qué es un algoritmo
Un algoritmo es una lista de pasos ordenados y bien definidos que permite resolver un problema o lograr un objetivo. Los algoritmos no son solo cosa de computadoras: los usás todos los días.
Cebar un mate es un algoritmo:
-
Poner la yerba en el mate.
-
Inclinar el mate y acomodar la yerba hacia un costado.
-
Echar un poco de agua tibia y esperar a que se absorba.
-
Echar agua caliente (no hirviendo) por el costado.
-
Poner la bombilla y tomar.
Para que una lista de pasos sea un buen algoritmo tiene que cumplir tres cosas: cada paso se entiende de una sola manera, el orden importa y termina en algún momento.
Definí con tus palabras qué es un algoritmo y escribí como lista de pasos numerados un algoritmo cotidiano, por ejemplo, para preparar mate o para cruzar la calle.
Definí con tus palabras qué es un algoritmo y escribí como lista de pasos numerados un algoritmo cotidiano, por ejemplo, para preparar mate o para cruzar la calle.
Búsqueda secuencial
Camila busca el nombre «Bruno» en una lista de compañeros. La forma más natural es empezar por el primero y revisar uno por uno hasta encontrarlo. Eso se llama búsqueda secuencial (o lineal).
Cada vez que miramos un elemento y lo comparamos con el buscado, hacemos una comparación. Las posiciones se cuentan desde 1.
¿Y si el número no está? Hay que revisar toda la lista para estar seguro. Con una lista de $n$ elementos, en el peor caso se hacen $n$ comparaciones: cuando el elemento está al final o no está.
Se aplica una búsqueda secuencial en la lista 7, 3, 9, 4, 1 para encontrar el número 4. Indicá en qué posición está (contando desde 1) y cuántos elementos se revisan…
Se aplica una búsqueda secuencial en la lista 7, 3, 9, 4, 1 para encontrar el número 4. Indicá en qué posición está (contando desde 1) y cuántos elementos se revisan hasta encontrarlo.
Camila busca el nombre «Bruno» en una lista de siete compañeros que no está ordenada: Martina, Facundo, Lucía, Bruno, Felipe, Micaela, Agustín. Describí paso a paso cómo…
Camila busca el nombre «Bruno» en una lista de siete compañeros que no está ordenada: Martina, Facundo, Lucía, Bruno, Felipe, Micaela, Agustín. Describí paso a paso cómo actúa una búsqueda secuencial y decí cuántas comparaciones se hacen hasta encontrarlo. Luego indicá cuántas comparaciones se harían si el nombre buscado fuera «Joaquín», que no está en la lista.
Búsqueda binaria
Cuando la lista está ordenada, se puede buscar mucho más rápido. Es como buscar una palabra en el diccionario: no empezás por la «A»; abrís por la mitad y decidís hacia dónde seguir.
La búsqueda binaria funciona así:
-
Mirá el elemento del medio.
-
Si es el buscado, terminaste.
-
Si el buscado es menor, descartá la mitad de la derecha. Si es mayor, descartá la de la izquierda.
-
Repetí con la mitad que quedó.
Se tiene la lista ordenada 3, 8, 12, 15, 21, 27, 34 y se busca el número 27 con búsqueda binaria (se mira el elemento del medio y se descarta la mitad donde no puede…
Se tiene la lista ordenada 3, 8, 12, 15, 21, 27, 34 y se busca el número 27 con búsqueda binaria (se mira el elemento del medio y se descarta la mitad donde no puede estar). Escribí cada paso: qué elemento del medio se mira y qué mitad se descarta, hasta encontrar el 27.
Florencia tiene una lista ordenada de 100 números y Mateo tiene una lista desordenada de 100 números. Ambos buscan un valor. Compará qué algoritmo de búsqueda puede usar…
Florencia tiene una lista ordenada de 100 números y Mateo tiene una lista desordenada de 100 números. Ambos buscan un valor. Compará qué algoritmo de búsqueda puede usar cada uno, cuántas comparaciones harían como máximo con la búsqueda secuencial y por qué la búsqueda binaria solo sirve en uno de los dos casos. Argumentá cuándo conviene ordenar antes una lista para luego buscar.
Ordenar por burbuja
Para ordenar una lista hay varios métodos. El de burbuja compara vecinos: recorre la lista de izquierda a derecha, y si dos elementos seguidos están en orden incorrecto, los intercambia. Cada recorrido completo es una pasada. Los números más grandes «suben» hacia el final como burbujas.
Se repiten las pasadas hasta que en una pasada no haya ningún cambio.
Se ordena de menor a mayor la lista 5, 2, 8, 1 comparando de a dos elementos vecinos y cambiándolos de lugar si están en el orden incorrecto. Escribí cómo queda la lista…
Se ordena de menor a mayor la lista 5, 2, 8, 1 comparando de a dos elementos vecinos y cambiándolos de lugar si están en el orden incorrecto. Escribí cómo queda la lista después de la primera pasada completa de izquierda a derecha.
Ordená de menor a mayor la lista 6, 4, 9, 2 con el método de ordenamiento por burbuja. Mostrá cómo queda la lista al final de cada pasada, y decí cuántas pasadas fueron…
Ordená de menor a mayor la lista 6, 4, 9, 2 con el método de ordenamiento por burbuja. Mostrá cómo queda la lista al final de cada pasada, y decí cuántas pasadas fueron necesarias hasta que no hubo más cambios.
Ordenar por selección y comparar métodos
Otro método es el de selección: en cada vuelta se busca el menor de los elementos que faltan colocar y se lo intercambia con el que está en la primera posición libre.
Los dos métodos llegan al mismo resultado, pero con distinta cantidad de pasos e intercambios. Para comparar, se sigue cada algoritmo a mano y se cuentan los intercambios.
| Burbuja | Selección | |
|---|---|---|
| Qué compara | Vecinos | Busca el menor de los que faltan |
| Cuándo termina | Cuando una pasada no tiene cambios | Cuando todos están colocados |
| Intercambios | Muchos, de a uno por vez | Como mucho uno por vuelta |
Se ordena de menor a mayor la lista 9, 7, 5, 3, 1 de dos maneras: por burbuja (comparando vecinos) y por selección (buscar el menor de los elementos restantes y…
Se ordena de menor a mayor la lista 9, 7, 5, 3, 1 de dos maneras: por burbuja (comparando vecinos) y por selección (buscar el menor de los elementos restantes y colocarlo en su lugar). Seguí los dos algoritmos y contá en cada uno cuántos intercambios se hacen. Después compará los resultados y explicá cuál realiza menos intercambios en este caso.
Volvé al principio: Valentina puede buscar su nombre con la búsqueda secuencial si la lista está desordenada; Mateo, para dejar la lista en orden alfabético, puede usar burbuja o selección. Y si la lista queda ordenada, las siguientes búsquedas pueden ser binarias.