Algoritmos de búsqueda y ordenación: eficiencia

La búsqueda pregunta si aparece un valor buscado y dónde. Una lista tiene posiciones numeradas llamadas índices. Python cuenta desde cero: en [7, 3, 9, 3, 5], el índice 0 contiene 7 y el índice 4 contiene 5. El valor y su índice responden a preguntas distintas.

Comprueba un elemento cada vez

La búsqueda lineal, también llamada búsqueda secuencial, empieza por el primer elemento y compara cada uno con el valor buscado. Devuelve el resultado en cuanto encuentra una coincidencia. Si la lista termina sin coincidencias, devuelve -1, nuestra señal de «no encontrado».

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

len(items) da el número de elementos. range(len(items)) proporciona todos los índices válidos, desde 0 hasta justo antes de la longitud. items[i] lee el valor del índice actual. Un return termina la función, así que una coincidencia posterior nunca sustituye a la primera.

Buscar 3 en la lista anterior procede así:

1. En el índice 0, compara 7 con 3. Son distintos, así que continúa.
2. En el índice 1, compara 3 con 3. Coinciden, así que devuelve el índice 1.

El resultado es el índice 1 tras dos comparaciones. El segundo 3, en el índice 3, nunca se comprueba. Buscar 4, en cambio, comprueba 7, 3, 9, 3 y 5, y después devuelve -1 tras cinco comparaciones. Que se devuelva el índice 1 significa el segundo elemento, no un elemento cuyo valor sea 1.

Cuenta el trabajo

Sea $n$ el número de elementos. Para una lista no vacía, el mejor caso es una comparación: el primer elemento coincide. El peor caso requiere $n$ comparaciones: el valor buscado está al final o ausente. Una lista vacía necesita cero comparaciones y devuelve -1.

Si un valor buscado aparece una vez y tiene la misma probabilidad de ocupar cualquier posición, su promedio de comparaciones es

Para 1000 elementos, son 500,5 comparaciones. Un promedio puede ser fraccionario aunque cada búsqueda individual realice un número entero de comparaciones. Este promedio describe esa distribución concreta de búsquedas con éxito; las búsquedas fallidas frecuentes aumentarían el promedio general.

Sitúa el resultado de fallo después del bucle

Un else: return -1 dentro del bucle abandonaría ante la primera discrepancia. En [7, 3, 9], rechazaría una búsqueda de 3 tras ver solo 7. La devolución que indica el fallo debe ir después del bucle, cuando se han descartado todas las posiciones.

La búsqueda lineal no necesita orden ni preparación. Funciona con números, palabras o registros comparados por un identificador. Una versión diseñada para datos ordenados puede detenerse al superar la posible posición del valor buscado: en [2, 5, 8, 12], ver 8 basta para descartar 6. El código anterior sigue recorriendo deliberadamente hasta encontrar una coincidencia o llegar al final.

Otras tareas relacionadas usan el mismo recorrido, pero otra regla de parada. Contar todas las apariciones, reunir todos los índices coincidentes y encontrar un elemento máximo exige inspeccionar toda la lista; encontrar la primera coincidencia permite devolver el resultado antes.

La búsqueda binaria aprovecha el orden para descartar posiciones sin comprobarlas individualmente. Su entrada debe estar ordenada de forma ascendente. También necesita acceso rápido al elemento de un índice elegido, como permiten un arreglo o una lista de Python.

Mantén un intervalo con ambos extremos incluidos

low y high marcan la primera y la última posición aún posibles, con ambos extremos incluidos. Empieza con low = 0 y high = len(items) - 1. Elige el índice central redondeando hacia abajo. Si el valor central es demasiado pequeño, todos los valores a su izquierda también lo son; mueve low más allá del centro. Si es demasiado grande, mueve high justo antes de él.

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

// divide y redondea hacia abajo. El bucle incluye el caso low == high porque queda una posición sin comprobar. Cuando low > high, el intervalo está vacío.

Sigue una búsqueda con coincidencia y otra sin ella

Usa [3, 8, 12, 17, 23, 31, 42, 56, 64, 77, 85], con índices de 0 a 10. Para encontrar 64, el primer índice central es 5 y contiene 31. Como 31 es demasiado pequeño, asigna low = 6. El siguiente índice central es 8 y contiene 64. Devuelve 8 tras dos comprobaciones de un elemento central.

Para buscar 20 en la misma lista:

Ahora el intervalo está vacío, así que devuelve -1. Este fallo está justificado: el orden respaldaba cada parte descartada.

Por qué es rápida

Cada comprobación sin coincidencia deja como máximo la mitad del intervalo. Para una lista no vacía, el número máximo de comprobaciones de un elemento central es $\lfloor {\log }_{2}n\rfloor +1$. El logaritmo en base 2 describe las divisiones sucesivas por la mitad: $2^{10}=1024$, así que mil elementos necesitan como máximo 10 comprobaciones; un millón necesita como máximo 20. Una comprobación en este código de Python puede realizar dos comparaciones, == y <. Las comprobaciones y las comparaciones son unidades de conteo distintas.

Condiciones y errores en los límites

El orden es esencial. Buscar 2 en [9, 2, 7, 4, 1] primero encuentra 7 y descarta la parte derecha; después encuentra 9 y descarta la coincidencia restante en el índice 1. El acceso rápido al centro también importa: seguir enlaces para llegar al centro de una lista enlazada pierde la ventaja de velocidad de la versión con arreglo.

Excluye siempre el centro comprobado tras una discrepancia. Usar low = mid puede dejar [10, 20] sin cambios para siempre al buscar 20. Usar while low < high omite el último candidato y falla al buscar 5 en [5]. En una lista vacía, high = -1, así que el bucle correcto nunca empieza.

Con duplicados, esta versión devuelve cualquier índice coincidente. Buscar 4 en [2, 4, 4, 4, 9] devuelve inmediatamente el índice 2; encontrar la primera aparición requiere una búsqueda modificada que continúe a la izquierda tras una coincidencia.

Ordenar consiste en reorganizar los elementos según una clave elegida. Para números en orden ascendente, cada elemento es menor o igual que el siguiente. «No decreciente» admite vecinos iguales: [2, 5, 5, 9] está ordenada. El orden descendente invierte el sentido.

Comprueba dos condiciones

Una ordenación correcta debe producir una salida en orden que contenga exactamente los elementos originales, conservando cada repetición. Ordenar [3, 1, 2] como [1, 2, 3] es correcto. Tanto [1, 2] como [1, 1, 3] fallan, aunque sus vecinos estén en orden. La primera pierde un elemento; la segunda cambia qué elementos aparecen. Una reorganización que conserva todas las apariciones se llama permutación.

En un registro, la clave es solo el campo usado para comparar. Las ciudades podrían ordenarse por nombre o población. Todo el registro de la ciudad se mueve cuando se mueve su clave de población; separar el nombre corrompería los datos.

El orden del texto depende de la clave

La comparación directa de texto sigue los códigos de caracteres, carácter a carácter. En ASCII y Unicode, A–Z usan los códigos 65–90 y a–z usan 97–122. Esto coloca «Zorro» antes que «abeja» en una comparación directa. Comparar copias en minúsculas permite ordenar estos ejemplos sin distinguir mayúsculas de minúsculas.

Los dígitos de un texto también se comportan como caracteres. «10» se ordena antes que «9» porque su primer carácter es «1». Una clave numérica convierte esas cadenas en los números que representan, situando 9 antes que 10. Decide qué significan los datos antes de elegir la comparación.

Mueve valores sin perderlos

Un intercambio permuta dos posiciones. Una variable temporal protege el valor que, de otro modo, se sobrescribiría:

temp = items[i]
items[i] = items[j]
items[j] = temp

Python también permite items[i], items[j] = items[j], items[i]. Escribir las dos asignaciones sin guardar el primer valor convierte [4, 7] en [7, 7]. La ordenación por burbuja y por selección mueven elementos mediante intercambios; la ordenación por mezcla los copia en una salida combinada.

Estabilidad y memoria

Una ordenación estable conserva el orden original de los registros cuyas claves son iguales. Empieza con Ana 85, Ben 92, Cara 85, en orden alfabético. Una ordenación estable por puntuación descendente produce Ben 92, Ana 85, Cara 85. Ana sigue antes que Cara. Así, una ordenación posterior por puntuación conserva el orden alfabético previo dentro de cada grupo de puntuación. La ordenación integrada de Python es estable.

Una ordenación in situ reorganiza la lista existente con solo unas pocas variables adicionales, independientemente de su longitud. Los métodos por burbuja y por selección que se enseñan aquí son in situ. La ordenación por mezcla habitual necesita almacenamiento adicional proporcional al número de elementos. La estabilidad y la memoria describen propiedades distintas: una ordenación puede ser in situ y, a la vez, inestable.

Mide el desorden con inversiones

Una inversión es un par de posiciones en el que la clave de un elemento anterior es mayor que la de uno posterior. En [5, 1, 4, 2, 8], las inversiones son (5, 1), (5, 4), (5, 2) y (4, 2): cuatro en total. Los pares no tienen por qué ser vecinos.

Una lista ordenada tiene cero inversiones. Una lista invertida de $n$ elementos distintos tiene $n(n-1)\mathrm{/}2$, el máximo. Las claves iguales nunca forman una inversión: [3, 3, 1] tiene dos, una por cada 3 antes del 1. Contar inversiones ayuda a explicar el número de intercambios de la ordenación por burbuja.

La ordenación por burbuja compara elementos vecinos de izquierda a derecha. Cuando el de la izquierda es mayor, intercambia el par. Cada recorrido es una pasada. Un elemento grande puede moverse repetidamente a la derecha durante una pasada, hasta que el mayor elemento restante alcanza su posición definitiva.

Sigue la primera pasada

Empieza con [5, 1, 4, 2, 8]:

1. Compara 5 y 1; intercámbialos para obtener [1, 5, 4, 2, 8].
2. Compara 5 y 4; intercámbialos para obtener [1, 4, 5, 2, 8].
3. Compara 5 y 2; intercámbialos para obtener [1, 4, 2, 5, 8].
4. Compara 5 y 8; déjalos como están.

La pasada realiza cuatro comparaciones y tres intercambios. El mayor elemento, 8, ya está colocado. El resto sigue sin ordenar: 4 precede a 2. Una pasada garantiza la posición definitiva del máximo, no el orden de todos los elementos.

La pasada 2 solo necesita las primeras cuatro posiciones. Compara 1 con 4, después intercambia 4 con 2 y luego compara 4 con 5. Esto da [1, 2, 4, 5, 8] tras tres comparaciones más y un intercambio. La pasada 3 compara 1 con 2 y 2 con 4. No realiza intercambios, lo que confirma que la lista está ordenada. Totales: nueve comparaciones y cuatro intercambios.

Acorta cada pasada y termina antes

def bubble_sort(items):
    n = len(items)
    for p in range(n - 1):
        swapped = False
        for j in range(n - 1 - p):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if not swapped:
            break

El contador de pasadas p empieza en cero. El mayor valor de j es n - 2 - p, así que j + 1 se mantiene dentro de la parte sin ordenar. Restablece swapped al principio de cada pasada; un intercambio en una pasada anterior no indica si la pasada actual ha movido algún elemento.

Tras cada pasada, una posición más de la derecha es definitiva. Una pasada sin intercambios demuestra que todos los vecinos comparados están en orden. El sufijo ya colocado también está en orden, así que el algoritmo puede detenerse. La pasada de confirmación también cuenta como trabajo.

Compara el mejor y el peor caso

Para una lista ordenada no vacía, la versión con terminación anticipada realiza $n-1$ comparaciones y cero intercambios. En una lista invertida de elementos distintos, realiza

comparaciones y el mismo número de intercambios. Cinco elementos necesitan 10; 1000 elementos necesitan 499 500. Sin terminación anticipada, el ejemplo resuelto de cinco elementos también ejecutaría su última pasada de una comparación, llegando a 10 comparaciones.

Cada intercambio elimina exactamente una inversión. Las cuatro inversiones de la lista original del ejemplo explican sus cuatro intercambios. Los vecinos iguales permanecen en su sitio porque la condición usa >, lo que hace que esta versión sea estable e in situ. Sustituir > por >= puede invertir registros con claves iguales.

La posición importa incluso cuando hay pocas inversiones. [5, 1, 2, 3, 4] usa cuatro intercambios y una segunda pasada para confirmar el orden, con siete comparaciones. [2, 3, 4, 5, 1] también necesita cuatro intercambios, pero su 1 solo puede moverse a la izquierda una vez por pasada. Necesita las cuatro pasadas y 10 comparaciones.

La ordenación por selección construye un prefijo ordenado a la izquierda. Cada pasada encuentra el menor elemento del sufijo restante y después lo intercambia hasta la siguiente posición del prefijo. El recorrido encuentra la posición; el intercambio ocurre después del recorrido.

Guarda un índice

En la posición i, empieza con smallest = i. Compara cada elemento posterior con items[smallest]. Actualiza smallest solo cuando aparezca un elemento menor. Cuando termine el recorrido, intercambia items[i] y items[smallest].

def selection_sort(items):
    n = len(items)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if items[j] < items[smallest]:
                smallest = j
        if smallest != i:
            items[i], items[smallest] = items[smallest], items[i]

Guardar solo el menor valor te dejaría sin su posición para el intercambio. Empezar el recorrido en el índice 0 volvería a visitar los elementos ya colocados; la búsqueda restante empieza justo después de i.

Sigue las pasadas

Empieza con [29, 10, 14, 37, 13].

El tercer mínimo ya está en su posición, así que ningún valor se mueve. Tras cuatro pasadas, el último elemento debe ser el mayor; no necesita una pasada aparte. Hay 10 comparaciones y tres intercambios que desplazan elementos. La condición del código omite los intercambios de una posición consigo misma; omitir esa condición no cambia el resultado.

Las comparaciones y los intercambios tienen costes distintos

La ordenación por selección siempre realiza $n(n-1)\mathrm{/}2$ comparaciones de elementos: cada pasada debe inspeccionar todo el sufijo restante para identificar su mínimo. El total es 10 para cinco elementos o 499 500 para 1000, incluso con una entrada ya ordenada. Un recorrido que no cambia ningún índice guardado identifica el mínimo de esa pasada, pero no garantiza en general que el sufijo restante esté ordenado.

Para una lista no vacía, hay como máximo un intercambio con desplazamiento por pasada y, por tanto, como máximo $n-1$ en total. Una entrada vacía no necesita pasadas ni intercambios. La ordenación por burbuja puede necesitar $n(n-1)\mathrm{/}2$ intercambios en una lista invertida de elementos distintos. Si mover registros grandes cuesta mucho más que comparar sus claves, el bajo número de intercambios de la ordenación por selección puede importar a pesar de sus numerosas comparaciones. Intercambiar cada vez que aparece un nuevo mínimo durante el recorrido pierde esa ventaja.

Las claves iguales pueden cambiar de orden

Este método basado en intercambios es in situ, pero inestable. Etiqueta los registros de igual clave como 4a y 4b para distinguirlos. Partiendo de [4a, 4b, 1], la primera pasada intercambia 4a y 1, produciendo [1, 4b, 4a]. Las claves iguales han invertido su orden original, aunque el algoritmo nunca las comparó directamente como desiguales. Conservar el primer mínimo encontrado durante un recorrido no impide que un intercambio entre posiciones alejadas salte por encima de un registro con la misma clave.

La mezcla combina dos listas ya ordenadas en una salida ordenada. Mantén un marcador en el primer elemento sin usar de cada entrada. Compara esos dos primeros elementos pendientes, copia el menor y avanza solo su marcador.

Elige el siguiente elemento menor

Mezcla [3, 27, 38, 43] con [9, 10, 82]:

La lista izquierda ya está vacía. Copia el 82 restante sin otra comparación de elementos. El resultado es [3, 9, 10, 27, 38, 43, 82], con seis comparaciones. Copiar el tramo restante forma parte del algoritmo: detenerse cuando terminan las comparaciones perdería datos.

¿Por qué puede el método ignorar los elementos posteriores a los primeros pendientes? Cada primer pendiente es el menor elemento restante de su propia lista. Por tanto, el menor de los dos es el menor elemento restante en total. Este razonamiento sigue siendo válido tras cada avance de un marcador porque las partes sin usar permanecen ordenadas.

Lee el código de mezcla

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

append añade un elemento. Un segmento como left[i:] contiene el tramo sin usar, y extend copia sus elementos. Solo uno de los tramos sin usar puede ser no vacío cuando termina el bucle. Si una entrada empieza vacía, el bucle realiza cero comparaciones y la otra lista se copia intacta.

Cuenta comparaciones y almacenamiento

Para dos listas no vacías de longitudes $m$ y $k$, se necesitan como máximo $m+k-1$ comparaciones entre primeros elementos pendientes. Cada comparación coloca un elemento y, como mínimo, el último puede copiarse sin comparar. El menor número posible de comparaciones de mezcla es la longitud de la lista más corta: mezclar [1, 2, 3] con [4, 5, 6] usa tres comparaciones antes de agotar la izquierda.

El trabajo total de copia crece con $m+k$ aunque las comparaciones terminen antes, porque todos los elementos deben aparecer en la salida. La lista nueva también necesita espacio para $m+k$ elementos. El número de comparaciones, el trabajo de copia y el almacenamiento adicional miden partes distintas de la misma operación.

Gestiona los empates y el orden de entrada

La condición <= toma de la izquierda cuando las claves son iguales. Si las dos entradas proceden de partes consecutivas de una lista original, esto conserva el registro anterior antes que el posterior de igual clave. Es la regla de desempate necesaria para una ordenación por mezcla estable.

El requisito de entradas ordenadas es indispensable. Mezclar [5, 1] con [3] copia 3 y después el tramo [5, 1], produciendo [3, 5, 1]. La regla del primer pendiente falló porque 5 no era el menor valor restante de su propia entrada.

La ordenación por mezcla resuelve una tarea grande de ordenación dividiéndola en tareas más pequeñas. Esto es divide y vencerás: divide la lista, ordena cada mitad y mezcla las mitades ordenadas.

Detén la división en el caso base

Una función es recursiva cuando se llama a sí misma. La ordenación por mezcla se llama a sí misma con listas más cortas. Su caso base devuelve sin cambios una lista de cero o un elemento, ya que esa lista está ordenada.

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)

Los segmentos dividen la entrada sin perder elementos. Para una longitud impar, el lado derecho tiene un elemento más: [6, 2, 9, 4, 1, 7, 3] se divide en [6, 2, 9] y [4, 1, 7, 3]. Ambas mitades son más cortas, así que las llamadas recursivas acaban alcanzando el caso base. Un caso base por sí solo no garantizaría la terminación si una llamada siguiera pasándose la lista original a sí misma.

Reconstruye la lista ordenada

Sigue [38, 27, 43, 3, 9, 82, 10, 15]. Se divide en dos mitades de cuatro elementos, después en cuatro partes de dos elementos y después en elementos individuales. La división no reorganiza los valores. El orden se construye durante las mezclas:

1. Mezcla elementos individuales para obtener [27, 38], [3, 43], [9, 82] y [10, 15]. Cada mezcla usa una comparación: cuatro en total.
2. Mezcla los pares para obtener [3, 27, 38, 43] y [9, 10, 15, 82]. Cada mezcla usa tres comparaciones: seis en total.
3. Mezcla esas mitades para obtener [3, 9, 10, 15, 27, 38, 43, 82]. Esto usa siete comparaciones.

La ordenación completa usa $4+6+7=17$ comparaciones de elementos. No cuentes solo la mezcla final: antes hubo que producir las mitades ordenadas. El ejemplo anterior de siete elementos se ordena como [1, 2, 3, 4, 6, 7, 9] usando 14 comparaciones con esta regla de división.

Cuenta los niveles y el trabajo por nivel

Para ocho elementos, dividir por la mitad llega a elementos individuales tras tres niveles porque $2^3=8$. En general, hay unos ${\log }_{2}n$ niveles de mezcla. En un nivel completo, las mezclas procesan conjuntamente los $n$ elementos. Por tanto, cada nivel realiza trabajo proporcional a $n$, lo que da un crecimiento como $n{\log }_{2}n$.

Para ocho elementos, $n{\log }_{2}n=24$ es una cota superior útil, aunque poco ajustada, para las comparaciones, no el conteo exacto. La lista del ejemplo usó 17; una lista de ocho elementos ya ordenada o invertida usa 12. El orden de entrada cambia cuándo una mezcla agota uno de sus lados, pero todas las listas siguen pasando por los niveles de división y mezcla. El crecimiento de las comparaciones sigue siendo $n\log n$ tanto en el mejor como en el peor caso para esta versión.

Para un millón de elementos, unos 20 niveles dan unos 20 millones de comparaciones como estimación del orden de magnitud superior. La ordenación por selección usa unos 500 mil millones. La diferencia crece rápidamente con el tamaño de la entrada.

Asume el coste del espacio adicional de salida

La ordenación por mezcla habitual basada en listas necesita almacenamiento adicional proporcional a $n$. Elegir el primer pendiente de la izquierda en los empates la hace estable.

Un tiempo de ejecución medido depende de la máquina y del programa. Un conteo de pasos describe el trabajo del algoritmo mediante una operación repetida elegida. El tamaño de la entrada, escrito $n$, es el número de elementos que se procesan.

Elige la operación antes de contar

En búsqueda y ordenación, las comparaciones entre valores de elementos suelen ser una operación básica útil. Cuenta los intercambios por separado cuando importe mover datos. Para la búsqueda binaria, conviene contar las comprobaciones de un elemento central. En la versión de Python, una comprobación central sin coincidencia evalúa tanto la igualdad como la relación de menor que, por lo que puede implicar dos comparaciones de elementos.

Estos conteos describen operaciones repetidas, no líneas de código. Una línea dentro de un bucle puede ejecutarse un millón de veces; varias líneas de preparación pueden ejecutarse una sola vez cada una.

Distingue los casos para un mismo tamaño

El mejor caso requiere el menor número de pasos entre las entradas válidas de tamaño $n$. El peor caso requiere el mayor número y ofrece una garantía. El caso promedio calcula el promedio para un patrón de entradas especificado.

Para una lista no vacía, la búsqueda lineal necesita una comparación si el valor buscado está al principio, y $n$ si está al final o ausente. Su promedio para búsquedas con éxito es $(n+1)\mathrm{/}2$ cuando la primera posición coincidente tiene la misma probabilidad de ser cualquier posición. La palabra «promedio» necesita esa distribución; no significa el punto medio entre los conteos del mejor y el peor caso para cualquier algoritmo.

Convierte los bucles en conteos

Una comparación por elemento en un recorrido completo da $n$ comparaciones. Dos bucles completos anidados, cada uno ejecutándose $n$ veces, ejecutan su cuerpo compartido $n^2$ veces. Otro patrón de bucles anidados compara cada par una sola vez:

for i in range(n):
    for j in range(i + 1, n):
        compare(items[i], items[j])

La primera iteración externa compara su elemento con $n-1$ elementos posteriores. La siguiente lo compara con $n-2$, y la última, con ninguno. El total es

Escribe la suma hacia delante y hacia atrás. Cada par alineado suma $n$, y hay $n-1$ pares. Su total es $n(n-1)$, el doble de la suma original. Para cinco elementos, $4+3+2+1=10$; para 1000, el número de pares es 499 500.

Reconoce las divisiones sucesivas por la mitad

Un bucle que reduce a la mitad su trabajo restante requiere unas ${\log }_{2}n$ repeticiones. Un millón baja por primera vez a 1 o menos tras 20 divisiones por la mitad: $2^{19}=524288$ y $2^{20}=1048576$ quedan a ambos lados de un millón. Esto difiere mucho de eliminar solo un elemento cada vez.

Para comparar crecimientos, conserva el término que crece más rápido. El conteo de pares es $n^2\mathrm{/}2-n\mathrm{/}2$. Con $n=1000$, sus términos son 500 000 y 500, por lo que el término cuadrático controla el crecimiento. Omitir el término menor y el factor constante describe la familia de crecimiento; no convierte el conteo exacto de 499 500 en un conteo exacto de un millón.

Una tasa de crecimiento describe cómo cambia la cantidad de trabajo al aumentar la entrada. Ayuda a comparar algoritmos más allá del tamaño concreto usado en un seguimiento.

Interpreta las familias habituales

En el crecimiento exponencial, añadir un solo elemento ya duplica el conteo: $2^{n+1}=2\times 2^n$. Duplicar la entrada es un cambio mucho mayor que añadir uno.

Compara tamaños con números

Para entradas de 10, 100, 1000 y un millón de elementos, ${\log }_{2}n$ es aproximadamente 3,3, 6,6, 10 y 20. Los valores correspondientes de $n{\log }_{2}n$ son aproximadamente 33, 664, 9966 y 20 millones. Los valores cuadráticos son 100, 10 000, un millón y un billón.

El crecimiento logarítmico no es «la mitad de la lista». Para un millón de elementos, dividir sucesivamente por la mitad requiere solo unas 20 etapas. Cuando la entrada pasa de 1000 a 2000, $n{\log }_{2}n$ pasa de unos 9966 a 21 932, un factor de aproximadamente 2,2. El logaritmo también cambia, así que el conteo crece algo más rápido que el lineal.

El trabajo exponencial aumenta rápidamente. $2^{10}=1024$ y $2^{20}$ es aproximadamente un millón. A mil millones de pasos por segundo, $2^{50}$ pasos siguen requiriendo unos 13 días. Añadir un elemento más duplica ese tiempo.

Usa las etiquetas O informales

Quienes programan suelen etiquetar estas familias como $O(1)$, $O(\log n)$, $O(n)$, $O(n\log n)$, $O(n^2)$ y $O(2^n)$. Aquí identifican la familia habitual de crecimiento del peor caso. Lee $O(n^2)$ como «orden n al cuadrado». La etiqueta omite factores constantes y términos de menor orden: $n(n-1)\mathrm{/}2$ comparaciones pertenece a la familia cuadrática.

Una etiqueta O no es un tiempo de ejecución exacto ni una cantidad de segundos. Tampoco afirma que toda entrada use el conteo del peor caso. La ordenación por burbuja con terminación anticipada tiene un mejor caso lineal, pero un peor caso cuadrático.

Encuentra el punto de cruce

Supón que el método A requiere $100n$ pasos y el método B, $n^2$. Con 50 elementos, A requiere 5000 pasos y B, 2500. Con 100, ambos requieren 10 000. Con 1000, A requiere 100 000 y B, un millón. El menor crecimiento de A acaba compensando su mayor factor constante.

La velocidad del hardware cambia la escala sin cambiar la familia. Una computadora 100 veces más rápida permite que un método cuadrático procese solo 10 veces más elementos en el mismo tiempo, ya que $(10n{)}^2=100n^2$. Un método lineal podría procesar 100 veces más. Para una tarea pequeña, la preparación y las constantes pueden dominar; para entradas grandes, el crecimiento resulta decisivo.

Un tiempo de ejecución conocido y un patrón de crecimiento permiten predecir cómo se comportará una tarea mayor. La predicción es una estimación porque el tiempo real también depende de la implementación, la memoria, el hardware y el resto del trabajo de la máquina.

Escala la entrada y después el tiempo

Para trabajo lineal, multiplica el tiempo por la razón entre los tamaños de entrada. Si una búsqueda en el peor caso entre un millón de elementos tarda 3 milisegundos, diez millones de elementos requieren unos 30 milisegundos en condiciones comparables.

Para trabajo cuadrático, eleva esa razón al cuadrado. Supón que la ordenación por selección tarda 2 segundos con 50 000 elementos. Duplicar a 100 000 elementos da

segundos. Aumentar a 500 000 elementos multiplica el tamaño de entrada por 10, así que el tiempo estimado es $2\times {10}^2=200$ segundos. Multiplicar el tiempo por 10 trataría incorrectamente el algoritmo como lineal.

Para un crecimiento $n{\log }_{2}n$, usa la razón entre las dos expresiones completas. Duplicar una entrada grande cuesta algo más del doble porque el logaritmo aumenta junto con el número de elementos.

Calcula hacia atrás desde el tiempo disponible

Usa el mismo tiempo cuadrático de referencia: 2 segundos para 50 000 elementos. Un tiempo disponible de 32 segundos permite multiplicar el tiempo por 16. La entrada puede crecer por un factor igual a la raíz cuadrada de 16, que es 4, dando unos 200 000 elementos. Comprueba el sentido sustituyendo: cuadruplicar la entrada predice multiplicar el tiempo por 16, pasando de 2 a 32 segundos.

Compara algoritmos con un tamaño grande

Para un millón de elementos, la ordenación por selección realiza 499 999 500 000 comparaciones, unos 500 mil millones. La ordenación por mezcla necesita como máximo unos 20 millones. A una velocidad hipotética de mil millones de comparaciones por segundo, esos conteos corresponden a unos 500 segundos frente a 0,02 segundos, una diferencia de aproximadamente 25 000 veces. Este cálculo supone el mismo coste por comparación para aislar el efecto del algoritmo; los programas medidos también tienen costes de movimiento y acceso a memoria.

Pon a prueba una predicción de crecimiento

Cronometra el mismo programa con varios tamaños que se dupliquen, como 10 000, 20 000 y 40 000 elementos. Divide cada tiempo por el anterior. Cocientes cercanos a 2 sugieren crecimiento lineal; algo superiores a 2 sugieren $n\log n$; cercanos a 4 sugieren crecimiento cuadrático.

Mantén la misma máquina y el mismo método de medición. Repite las ejecuciones y usa tamaños suficientemente grandes para que el tiempo de inicio no domine. Compara casos semejantes: buscar en la primera posición con un tamaño y hacer una búsqueda fallida con otro mezclaría los efectos de la entrada con el crecimiento. En la ordenación por burbuja, las listas ordenadas y las invertidas necesitan etiquetas de caso distintas.

Si al duplicar los tamaños obtienes 0,04, 0,16 y 0,64 segundos, ambos cocientes son 4, lo que respalda un modelo cuadrático en ese intervalo. Un cociente aislado con variaciones aleatorias aporta menos evidencia que un patrón repetido. Los conteos de pasos de un seguimiento especificado pueden ser exactos; una predicción en segundos debe decir «aproximadamente» y contrastarse con mediciones.

Un algoritmo correcto termina con toda entrada válida y produce la salida requerida. Una especificación indica la condición de entrada y el resultado prometido. Para la búsqueda binaria, la precondición es el orden ascendente. La poscondición es un índice coincidente, o -1 exactamente cuando el valor buscado está ausente.

Usa un invariante para conectar los pasos

Un invariante de bucle es una afirmación que se cumple antes de empezar el bucle y se conserva en cada repetición. Una justificación de corrección comprueba su inicio, su conservación y lo que implica cuando termina el bucle. Por separado, un argumento de terminación demuestra que el bucle acaba.

Para la ordenación por selección, usa este invariante: antes de la pasada i, las primeras i posiciones contienen los i elementos menores en orden.

1. Inicio: antes de la pasada 0, el prefijo está vacío. Ya cumple la afirmación.
2. Conservación: la pasada encuentra el menor elemento restante. Colocarlo a continuación amplía el prefijo ordenado en un elemento, y ese elemento es mayor o igual que todos los ya colocados.
3. Final: tras como máximo $n-1$ pasadas, solo el mayor elemento queda fuera del prefijo. Toda la lista está ordenada.

Cada movimiento es un intercambio, así que el multiconjunto de elementos también permanece igual. Una salida en orden, por sí sola, no cumpliría toda la especificación de ordenación.

La ordenación por burbuja usa un invariante del sufijo: tras $k$ pasadas, las últimas $k$ posiciones contienen los $k$ elementos mayores en orden. La siguiente pasada lleva el mayor elemento sin ordenar a ese sufijo. Una pasada sin intercambios establece el orden en toda la parte restante y permite terminar antes.

Explica los intervalos que descarta la búsqueda binaria

Usa el invariante: si aparece el valor buscado, al menos una aparición está dentro del intervalo de low a high, con ambos extremos incluidos. Al inicio, ese intervalo abarca toda la lista. Si el valor central es demasiado pequeño, el orden hace que todos los valores en mid o a su izquierda sean demasiado pequeños. Actualizar low a mid + 1 conserva todas las coincidencias posibles. La actualización a high = mid - 1 sigue el mismo razonamiento para valores demasiado grandes.

Si hay una coincidencia, la posición devuelta cumple directamente la poscondición. Si el intervalo se vacía, el invariante descarta el valor buscado en cualquier parte de la lista. La entrada sigue ordenada porque la búsqueda nunca la modifica.

Demuestra por qué termina la ejecución

Una medida entera no negativa que disminuye demuestra el avance hacia un final. En la búsqueda binaria, el número de posiciones candidatas disminuye estrictamente tras cada discrepancia. Se excluye la posición central comprobada, por lo que el bucle no puede mantener el mismo intervalo para siempre. La ordenación por burbuja y por selección realizan como máximo $n-1$ pasadas con una entrada no vacía y ninguna con una entrada vacía.

La ordenación por mezcla llega a listas de cero o un elemento porque cada llamada recursiva usa una lista más corta. Esos casos base están ordenados. Suponiendo que las llamadas con listas más cortas devuelven mitades correctamente ordenadas, la mezcla toma repetidamente el menor elemento restante y conserva todos los elementos. Esto lleva la corrección de vuelta hasta la llamada original.

Usa las pruebas para otra función

Una prueba compara un resultado real con uno esperado. Superar muchas pruebas seleccionadas aumenta la confianza, mientras que una sola entrada válida que falla es un contraejemplo que refuta la corrección. Un argumento general con un invariante abarca la familia ilimitada de entradas posibles que una colección finita de pruebas de ejemplo deja sin comprobar. Las pruebas son especialmente útiles para comprobar si el código real implementa el método usado en el argumento.

Un caso límite es una entrada válida cercana a un límite donde es fácil equivocarse con los supuestos y los límites de los bucles. Prevé el resultado esperado a partir de la especificación antes de ejecutar el código. De lo contrario, una salida errónea del programa puede acabar convirtiéndose sin que lo notes en tu respuesta esperada.

Elige listas que pongan a prueba los límites

Prueba listas vacías, de un elemento y de dos elementos; listas ya ordenadas e invertidas; valores repetidos y todos iguales; números negativos; y longitudes pares e impares. Para las búsquedas, incluye la primera posición, la última y valores buscados ausentes por debajo, por encima y entre los valores almacenados.

Una búsqueda binaria vacía debe devolver -1 sin acceder a ningún elemento: low = 0 y high = -1 hacen que el intervalo inicial esté vacío. Ordenar [3, 3, 3] debe devolver tres copias de 3. Una salida [3] estaría ordenada, pero no conservaría los elementos.

Sigue el fallo más pequeño

Una búsqueda binaria que usa while low < high no entra en el bucle para [5] con valor buscado 5. La corrección es low <= high, ya que un intervalo de una posición aún contiene un candidato. Esta prueba de un elemento aísla el límite con más claridad que una lista larga.

Con low = mid, buscar 20 en [10, 20] fija el centro en 0, encuentra 10 y deja low en 0. El intervalo no cambia en la siguiente repetición. Usa low = mid + 1 para excluir una posición ya comprobada. Una lista de dos elementos con el valor buscado al final revela este bucle infinito.

La ordenación por burbuja compara items[j] con items[j + 1]. En la primera pasada, el último índice izquierdo válido es n - 2. Continuar hasta n - 1 lee más allá de la lista y provoca el IndexError de Python. Este error de una posición en un límite se llama error de desfase de una unidad.

Comprueba las dos promesas de la salida

Para una ordenación, comprueba el orden entre vecinos y el número de apariciones de cada elemento original. Usa registros etiquetados para probar la estabilidad. Ana 85, Ben 92, Cara 85 debe conservar a Ana antes que Cara cuando una ordenación estable por puntuación agrupe las puntuaciones iguales. Una comprobación solo de puntuaciones no detectaría un intercambio de esos dos registros.

Genera también listas aleatorias. Compara sus resultados con una implementación de confianza, como sorted de Python. Incluye duplicados y distintas longitudes en las entradas generadas. Cuando falle una prueba, reduce la entrada conservando el fallo y después síguela a mano. Guarda el ejemplo pequeño como prueba de regresión para que el error corregido siga siendo detectable.

Calcula el centro sin desbordamientos

Los enteros de Python crecen según se necesita, así que (low + high) // 2 no se desborda. Algunos lenguajes usan enteros de ancho fijo. Con índices no negativos muy grandes, su suma puede superar el rango representable. La suma de enteros de Java da la vuelta al desbordarse; el desbordamiento de enteros con signo en C tiene un comportamiento indefinido.

Con índices válidos y low <= high, calcula en su lugar low + (high - low) // 2. La diferencia es no negativa y el resultado queda entre los extremos. Esto calcula la misma posición central redondeada hacia abajo sin formar la suma que podría desbordarse. Aquí se combinan las pruebas de límites y el razonamiento sobre la representación numérica del lenguaje.

Un algoritmo se adapta a una tarea cuando sus requisitos y costes encajan con los datos y el trabajo realizado. Considera el orden de entrada, el acceso a posiciones, el número de operaciones futuras, la memoria adicional, la estabilidad y el coste de mover registros.

Compara los métodos

La búsqueda binaria también necesita orden y acceso rápido al centro. Una buena comparación incluye esos requisitos; un conteo pequeño de búsqueda por sí solo omite el coste de preparar datos inadecuados.

Decide si compensa ordenar primero

Para una búsqueda entre un millón de elementos sin ordenar, la búsqueda lineal cuesta como máximo un millón de comparaciones. Ordenar primero por mezcla cuesta unos 20 millones de comparaciones antes de la primera búsqueda binaria, que después necesita como máximo 20 comprobaciones centrales. La preparación supera con creces el ahorro en esa única consulta.

Para 100 consultas sobre una lista que no cambia, las búsquedas lineales repetidas pueden costar 100 millones de comparaciones. Ordenar una vez y realizar 100 búsquedas binarias cuesta unos 20 millones de comparaciones más 2000 comprobaciones centrales. La preparación se reutiliza, lo que hace atractivo el segundo plan. Con este modelo aproximado de costes, el punto de equilibrio está en unas 20 búsquedas. La estimación depende de costes de operación comparables y recorridos en el peor caso; no es un umbral universal de consultas.

Sopesa el orden, el movimiento y la memoria

La ordenación por burbuja puede terminar rápido cuando solo hay un par cercano fuera de lugar. [1, 2, 4, 3, 5] necesita un intercambio en su primera pasada y una segunda para confirmar el orden: siete comparaciones. Pero «casi ordenada» no garantiza pocas pasadas. Un valor pequeño en el extremo derecho solo puede moverse una posición a la izquierda por pasada.

Los pocos intercambios de la ordenación por selección ayudan cuando mover registros es costoso. Tanto la ordenación por selección como por burbuja usan solo una cantidad fija de almacenamiento adicional. La ordenación por mezcla procesa listas grandes con un crecimiento del tiempo mucho menor, pero su forma habitual basada en listas necesita espacio para aproximadamente otra lista de elementos.

Si los registros de igual clave deben conservar el orden anterior, elige un método estable. Una lista ya alfabética por nombre puede ordenarse de forma estable por nota y seguir siendo alfabética dentro de cada grupo de notas. La ordenación por selección habitual puede alterar esos empates.

Usa herramientas de biblioteca probadas

Los programas reales suelen usar la ordenación integrada del lenguaje. La ordenación estable de Python usa un método adaptativo basado en mezclas, habitualmente llamado Timsort, que aprovecha el orden ya presente en la entrada. sorted(items) devuelve una lista nueva, mientras que items.sort() modifica la existente. Un método cuya interfaz modifica una lista in situ puede usar memoria de trabajo temporal internamente; no tiene por qué cumplir la definición de almacenamiento adicional fijo usada para las ordenaciones sencillas anteriores.

Para unos pocos elementos, un código sencillo y claro puede importar más que el crecimiento. Para colecciones grandes, compara el comportamiento en el peor caso y la memoria junto con las propiedades que realmente exige la tarea.