31.Búsqueda y ordenamiento

Buscar es encontrar si un dato está en una colección y en qué posición. Ordenar es acomodar los datos de menor a mayor (o al revés). Son de los problemas más clásicos de la programación.

Piensa en una pila de exámenes: para encontrar el de un alumno puedes revisar uno por uno (búsqueda lineal); si están en orden alfabético, abres por la mitad y descartas la mitad que no sirve (búsqueda binaria), mucho más rápido.

Búsqueda lineal

PSeInt:

Algoritmo BusquedaLineal
	Definir datos, buscado, i, posicion Como Entero
	Dimension datos[6]
	datos[1] <- 42
	datos[2] <- 7
	datos[3] <- 19
	datos[4] <- 88
	datos[5] <- 3
	datos[6] <- 56
	Escribir "Número a buscar:"
	Leer buscado
	posicion <- 0
	Para i <- 1 Hasta 6 Hacer
		Si datos[i] = buscado Y posicion = 0 Entonces
			posicion <- i
		FinSi
	FinPara
	Si posicion > 0 Entonces
		Escribir "Encontrado en la posición ", posicion
	SiNo
		Escribir "No está"
	FinSi
FinAlgoritmo

Python:

def busqueda_lineal(lista, buscado):
    for i, valor in enumerate(lista):
        if valor == buscado:
            return i
    return -1

datos = [42, 7, 19, 88, 3, 56]
print(busqueda_lineal(datos, 88))   # 3
print(busqueda_lineal(datos, 10))   # -1

Ordenamiento burbuja

PSeInt:

Algoritmo Burbuja
	Definir datos, i, j, aux Como Entero
	Dimension datos[5]
	datos[1] <- 5
	datos[2] <- 2
	datos[3] <- 9
	datos[4] <- 1
	datos[5] <- 7
	Para i <- 1 Hasta 4 Hacer
		Para j <- 1 Hasta 5 - i Hacer
			Si datos[j] > datos[j + 1] Entonces
				aux <- datos[j]
				datos[j] <- datos[j + 1]
				datos[j + 1] <- aux
			FinSi
		FinPara
	FinPara
	Para i <- 1 Hasta 5 Hacer
		Escribir Sin Saltar datos[i], " "
	FinPara
FinAlgoritmo

Python:

def burbuja(lista):
    datos = lista[:]                       # trabajar sobre una copia
    n = len(datos)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if datos[j] > datos[j + 1]:
                datos[j], datos[j + 1] = datos[j + 1], datos[j]
    return datos

print(burbuja([5, 2, 9, 1, 7]))   # [1, 2, 5, 7, 9]

En cada vuelta, el mayor de los que faltan «sube» al final, como una burbuja.

Problema: buscar una matrícula en una lista ordenada con búsqueda binaria, y contar cuántos pasos se necesitaron.

def busqueda_binaria(lista, buscado):
    inicio, fin = 0, len(lista) - 1
    pasos = 0
    while inicio <= fin:
        pasos += 1
        medio = (inicio + fin) // 2
        if lista[medio] == buscado:
            return medio, pasos
        elif lista[medio] < buscado:
            inicio = medio + 1     # está en la mitad derecha
        else:
            fin = medio - 1        # está en la mitad izquierda
    return -1, pasos

matriculas = list(range(1000, 2000))   # 1000 matrículas ordenadas
posicion, pasos = busqueda_binaria(matriculas, 1734)
print("Posición:", posicion, "en", pasos, "pasos")

Salida esperada:

Posición: 734 en 10 pasos

Con búsqueda lineal habría necesitado 735 comparaciones.

Ordenar en Python sin programar el algoritmo

alumnos = [("Luis", 7.4), ("Ana", 9.1), ("Sofía", 8.2)]
print(sorted(alumnos))                                    # por nombre
print(sorted(alumnos, key=lambda a: a[1], reverse=True))  # por promedio, de mayor a menor

# ✗ Error lógico: la lista no está ordenada y no encuentra el 88
def binaria(lista, x):
    i, f = 0, len(lista) - 1
    while i <= f:
        m = (i + f) // 2
        if lista[m] == x:
            return m
        if lista[m] < x:
            i = m + 1
        else:
            f = m - 1
    return -1

print(binaria([42, 7, 19, 88, 3, 56], 88))   # -1

# ✗ Error lógico
numeros = [3, 1, 2]
ordenados = numeros.sort()
print(ordenados)   # None

• Aprende los algoritmos clásicos para entender cómo funcionan, pero en programas reales usa sorted(), .sort(), in y bisect.
• Ordena con key para criterios personalizados (por promedio, por apellido).
• Si buscas muchas veces en los mismos datos, ordénalos una vez y usa búsqueda binaria, o usa un diccionario.
• Prueba con casos especiales: lista vacía, un elemento, elementos repetidos, el dato al principio y al final.

• Python Software Foundation. Guía para ordenar (Sorting HOW TO). https://docs.python.org/es/3/howto/sorting.html
• Python Software Foundation. bisect — Algoritmo de bisección de arreglos. https://docs.python.org/es/3/library/bisect.html
• Cormen, T., Leiserson, C., Rivest, R. y Stein, C. Introduction to Algorithms (4.ª ed.). MIT Press.
• Joyanes Aguilar, L. Fundamentos de programación. McGraw-Hill, capítulo de ordenación y búsqueda.