Búsqueda y ordenamiento

Búsqueda lineal

La búsqueda lineal revisa la lista elemento por elemento, de izquierda a derecha, y compara cada uno con el valor buscado. Se detiene cuando lo encuentra o cuando llega al final sin encontrarlo.

Es como buscar tu nombre en una lista pegada en la puerta del centro escolar: empezás por arriba y bajás con el dedo.

Por qué funciona con cualquier lista: no necesita ninguna condición, porque no se salta ningún elemento. Por eso es segura, aunque lenta cuando la lista es larga.

Leer lista, buscado

Para i desde 0 hasta longitud(lista) - 1 hacer

    Si lista[i] == buscado Entonces

        Escribir "Encontrado en la posición ", i

    Fin Si

Fin Para

En el peor caso (el valor está al final o no está) se compara con todos los elementos: en una lista de $n$ elementos son $n$ comparaciones.

Búsqueda binaria

La búsqueda binaria solo funciona si la lista está ordenada. En cada paso compara el valor buscado con el elemento del medio y descarta la mitad donde seguro no puede estar.

Es como buscar una palabra en el diccionario: abrís por la mitad, ves si te pasaste o te faltó, y seguís con la mitad que corresponde.

Por qué necesita orden: si el elemento del medio es menor que lo buscado, en una lista ordenada todo lo que está a su izquierda es aún menor, así que se puede descartar sin mirarlo. Sin orden, esa conclusión sería falsa.

Pasos del algoritmo:

1. Tomá los extremos: inicio y fin.

2. Calculá la posición del medio: medio = (inicio + fin) div 2 (parte entera).

3. Si lista[medio] es el buscado, terminaste.

4. Si es menor que el buscado, descartá la izquierda: inicio = medio + 1.

5. Si es mayor, descartá la derecha: fin = medio - 1.

6. Repetí mientras inicio <= fin. Si se cruzan, el valor no está.

Bubble Sort

Bubble Sort (ordenamiento de burbuja) ordena comparando pares vecinos: si el de la izquierda es mayor que el de la derecha, se intercambian. Al terminar una pasada, el mayor valor "sube como burbuja" hasta el final.

Por qué funciona: cada pasada lleva el mayor de los elementos pendientes a su lugar definitivo. Si hay $n$ elementos, bastan como máximo $n-1$ pasadas.

Para pasada desde 1 hasta n - 1 hacer

    Para i desde 0 hasta n - 2 hacer

        Si lista[i] > lista[i+1] Entonces

            intercambiar lista[i] y lista[i+1]

        Fin Si

    Fin Para

Fin Para

Selection Sort

Selection Sort (ordenamiento por selección) hace otra cosa: en cada paso busca el mínimo de la parte que falta ordenar y lo intercambia con el elemento de la primera posición pendiente.

Por qué funciona: después del paso 1, la posición 0 tiene el menor de toda la lista; después del paso 2, la posición 1 tiene el segundo menor, y así hasta el final.

Para i desde 0 hasta n - 2 hacer

    posMin = i

    Para j desde i + 1 hasta n - 1 hacer

        Si lista[j] < lista[posMin] Entonces

            posMin = j

        Fin Si

    Fin Para

    intercambiar lista[i] y lista[posMin]

Fin Para

Cuál conviene usar

Volvamos a la lista de don Ernesto: 1,000 códigos.

Con búsqueda lineal, en el peor caso se hacen 1,000 comparaciones. Con búsqueda binaria, cada paso descarta la mitad: 1,000 → 500 → 250 → … Como $2^{10} = 1{,}024$, bastan 10 comparaciones como máximo.

Entonces, ¿siempre conviene ordenar y usar binaria? No necesariamente. Ordenar cuesta trabajo. Si vas a buscar muchas veces, ordenar una vez y usar binaria vale la pena. Si buscás una sola vez en una lista desordenada, la lineal es más sencilla y suficiente.

Volvé al principio: don Ernesto puede ordenar sus códigos una vez y, desde entonces, encontrar cualquier producto en unas 10 comparaciones en vez de 1,000.

Resumen

• Búsqueda lineal: revisa uno por uno; sirve con cualquier lista; en el peor caso hace $n$ comparaciones.

• Búsqueda binaria: compara con el medio y descarta una mitad; exige lista ordenada; con 1,000 datos hace como máximo 10 comparaciones.

• Bubble Sort: compara vecinos e intercambia; cada pasada deja el mayor al final.

• Selection Sort: busca el mínimo de lo pendiente y lo intercambia a su posición; hace pocos intercambios.

• Las posiciones empiezan en 0; conviene escribir la lista después de cada paso.