Algoritmos de busca e ordenação e sua eficiência

Uma busca verifica se um valor procurado aparece e onde ele aparece. Uma lista tem posições numeradas chamadas índices. Python conta a partir de zero: em [7, 3, 9, 3, 5], o índice 0 contém 7 e o índice 4 contém 5. O valor e seu índice respondem a perguntas diferentes.

Verifique um elemento por vez

A busca linear, também chamada de busca sequencial, começa no primeiro elemento e compara cada elemento com o valor procurado. Ela retorna imediatamente quando encontra uma correspondência. Se a lista terminar sem uma correspondência, retorna -1, nosso sinal para “não encontrado”.

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

len(items) fornece o número de elementos. range(len(items)) fornece todos os índices válidos, começando em 0 e terminando logo antes do comprimento. items[i] lê o valor no índice atual. Um return encerra a função, portanto uma correspondência posterior nunca substitui a primeira.

A busca por 3 na lista acima ocorre da seguinte forma:

1. No índice 0, compare 7 com 3. São diferentes, então continue.
2. No índice 1, compare 3 com 3. São iguais, então retorne o índice 1.

O resultado é o índice 1 após duas comparações. O segundo 3, no índice 3, nunca é verificado. Buscar 4 verifica 7, 3, 9, 3 e 5 e depois retorna -1 após cinco comparações. Um índice retornado igual a 1 indica o segundo elemento, não um elemento cujo valor é 1.

Conte o trabalho

Seja $n$ o número de elementos. Para uma lista não vazia, o melhor caso é uma comparação: o primeiro elemento corresponde ao valor procurado. O pior caso são $n$ comparações: o valor procurado está no fim ou ausente. Uma lista vazia precisa de zero comparações e retorna -1.

Se um valor procurado aparece uma vez e tem a mesma probabilidade de ocupar qualquer posição, sua contagem média de comparações é

Para 1.000 elementos, são 500,5 comparações. Uma média pode ser fracionária mesmo que cada busca individual faça um número inteiro de comparações. Essa média descreve essa distribuição específica de buscas bem-sucedidas; buscas sem sucesso frequentes aumentariam a média geral.

Coloque o retorno de falha após o laço

Um else: return -1 dentro do laço desistiria na primeira não correspondência. Em [7, 3, 9], rejeitaria uma busca por 3 depois de ver apenas 7. O retorno de falha deve ficar após o laço, quando todas as posições tiverem sido descartadas.

A busca linear não precisa de ordem nem de preparação. Ela funciona com números, palavras ou registros comparados por um identificador. Uma versão projetada para dados ordenados pode parar quando passa pela posição possível do valor procurado: em [2, 5, 8, 12], ver 8 basta para descartar 6. O código acima continua deliberadamente a busca até encontrar uma correspondência ou chegar ao fim.

Tarefas relacionadas usam a mesma varredura, mas com uma regra de parada diferente. Contar todas as ocorrências, coletar todos os índices correspondentes e encontrar o maior elemento exigem inspecionar a lista inteira; encontrar a primeira correspondência permite um retorno antecipado.

A busca binária usa a ordem para descartar posições sem verificá-las individualmente. Sua entrada deve estar em ordem crescente. Ela também precisa de acesso rápido a um elemento em um índice escolhido, como um array ou uma lista Python oferece.

Mantenha um intervalo inclusivo

low e high marcam a primeira e a última posições ainda possíveis, incluindo os dois extremos. Comece com low = 0 e high = len(items) - 1. Escolha o índice central arredondando para baixo. Se o valor central for pequeno demais, todos os valores à sua esquerda também serão pequenos demais; mova low para depois do centro. Se for grande demais, mova high para imediatamente antes dele.

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 e arredonda para baixo. O laço inclui o caso low == high porque resta uma posição não verificada. Quando low > high, o intervalo está vazio.

Rastreie uma busca com sucesso e outra sem sucesso

Use [3, 8, 12, 17, 23, 31, 42, 56, 64, 77, 85], com índices de 0 a 10. Para encontrar 64, o primeiro índice central é 5, que contém 31. Como 31 é pequeno demais, defina low = 6. O próximo índice central é 8, que contém 64. Retorne 8 após duas verificações de elementos centrais.

Para buscar 20 na mesma lista:

Agora o intervalo está vazio, então retorne -1. Essa falha é justificada: a ordem da lista justificou cada parte descartada.

Por que é rápida

Cada verificação sem sucesso deixa no máximo metade do intervalo. Para uma lista não vazia, o número máximo de verificações de elementos centrais é $\lfloor {\log }_{2}n\rfloor +1$. O logaritmo de base 2 descreve divisões sucessivas pela metade: $2^{10}=1.024$, então mil elementos precisam de no máximo 10 verificações; um milhão precisa de no máximo 20. Uma verificação nesse código Python pode fazer duas comparações, == e <. Verificações e comparações são unidades de contagem diferentes.

Condições e erros nos limites

A ordem é essencial. Ao buscar 2 em [9, 2, 7, 4, 1], a busca vê primeiro 7 e descarta a parte direita, depois vê 9 e descarta a correspondência restante no índice 1. O acesso rápido ao meio também importa: seguir enlaces para alcançar o meio de uma lista encadeada elimina a vantagem de velocidade da versão com array.

Sempre exclua o elemento central testado após uma não correspondência. Usar low = mid pode deixar [10, 20] inalterada para sempre ao buscar 20. Usar while low < high ignora o último candidato e falha ao buscar 5 em [5]. Em uma lista vazia, high = -1, portanto o laço correto nunca começa.

Com duplicatas, esta versão retorna qualquer índice correspondente. Buscar 4 em [2, 4, 4, 4, 9] retorna imediatamente o índice 2; encontrar a primeira ocorrência exige uma busca modificada que continue para a esquerda após uma correspondência.

A ordenação reorganiza elementos por uma chave escolhida. Para números em ordem crescente, cada elemento é menor ou igual ao seguinte. “Não decrescente” permite vizinhos iguais: [2, 5, 5, 9] está ordenada. A ordem decrescente inverte a direção.

Verifique duas condições

Uma ordenação correta deve produzir uma saída em ordem que contenha exatamente os elementos originais, com todas as repetições preservadas. Ordenar [3, 1, 2] como [1, 2, 3] funciona. Tanto [1, 2] quanto [1, 1, 3] falham, embora seus vizinhos estejam em ordem. A primeira perde um elemento; a segunda altera os elementos presentes. Um rearranjo que preserva todas as ocorrências é chamado de permutação.

Em um registro, a chave é apenas o campo usado para comparação. Cidades poderiam ser ordenadas por nome ou população. O registro inteiro da cidade se move quando sua chave de população se move; separar o nome corromperia os dados.

A ordem do texto depende da chave

A comparação simples de textos segue os códigos de caracteres, um caractere por vez. Em ASCII e Unicode, A a Z usam os códigos 65 a 90 e a a z usam 97 a 122. Isso coloca “Zebra” antes de “apple” em uma comparação simples. Comparar cópias em letras minúsculas pode fornecer uma ordem que ignora maiúsculas e minúsculas nesses exemplos.

Dígitos em texto também se comportam como caracteres. “10” aparece antes de “9” porque seu primeiro caractere é “1”. Uma chave numérica converte essas cadeias de caracteres nos números que representam, colocando 9 antes de 10. Decida o que os dados significam antes de escolher a comparação.

Mova valores sem perdê-los

Uma troca permuta duas posições. Uma variável temporária protege o valor que seria sobrescrito:

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

Python também permite items[i], items[j] = items[j], items[i]. Escrever as duas atribuições sem guardar o primeiro valor transforma [4, 7] em [7, 7]. A ordenação por bolha e a por seleção movem elementos por meio de trocas; a ordenação por intercalação copia elementos para a saída intercalada.

Estabilidade e memória

Uma ordenação estável mantém a ordem original dos registros cujas chaves são iguais. Comece com Ana 85, Ben 92, Cara 85, em ordem alfabética. Uma ordenação estável por nota decrescente produz Ben 92, Ana 85, Cara 85. Ana permanece antes de Cara. Isso permite que uma ordenação posterior por nota preserve uma ordem alfabética anterior dentro de cada grupo de notas. A ordenação integrada do Python é estável.

Uma ordenação no próprio local reorganiza a lista existente com apenas algumas variáveis extras, independentemente de seu comprimento. Os métodos por bolha e por seleção ensinados aqui funcionam no próprio local. A ordenação por intercalação usual precisa de armazenamento extra proporcional ao número de elementos. Estabilidade e memória descrevem propriedades diferentes: uma ordenação pode funcionar no próprio local e ainda assim ser instável.

Meça a desordem com inversões

Uma inversão é um par de posições em que a chave de um elemento anterior é maior que a de um elemento posterior. Em [5, 1, 4, 2, 8], as inversões são (5, 1), (5, 4), (5, 2) e (4, 2): quatro no total. Os pares não precisam ser vizinhos.

Uma lista ordenada tem zero inversões. Uma lista de $n$ elementos distintos em ordem inversa tem $n(n-1)\mathrm{/}2$, o máximo. Chaves iguais nunca formam uma inversão: [3, 3, 1] tem duas, uma para cada 3 antes de 1. Contar inversões é útil para explicar a contagem de trocas da ordenação por bolha.

A ordenação por bolha compara elementos vizinhos da esquerda para a direita. Quando o elemento da esquerda é maior, ela troca o par. Cada percurso é uma passada. Um elemento grande pode se mover repetidamente para a direita durante uma passada, até que o maior elemento restante alcance sua posição final.

Acompanhe a primeira passada

Comece com [5, 1, 4, 2, 8]:

1. Compare 5 e 1; troque para obter [1, 5, 4, 2, 8].
2. Compare 5 e 4; troque para obter [1, 4, 5, 2, 8].
3. Compare 5 e 2; troque para obter [1, 4, 2, 5, 8].
4. Compare 5 e 8; deixe-os como estão.

A passada faz quatro comparações e três trocas. O maior elemento, 8, está posicionado. O restante ainda não está ordenado: 4 precede 2. Uma passada garante a posição final do máximo, não a ordem de todos os elementos.

A passada 2 precisa apenas das primeiras quatro posições. Compare 1 com 4, depois troque 4 com 2 e compare 4 com 5. Isso produz [1, 2, 4, 5, 8] após mais três comparações e uma troca. A passada 3 compara 1 com 2 e 2 com 4. Ela não faz trocas, confirmando que a lista está ordenada. Totais: nove comparações e quatro trocas.

Encurte cada passada e pare antecipadamente

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

O contador de passadas p começa em zero. O maior valor de j é n - 2 - p, portanto j + 1 permanece dentro da parte não ordenada. Reinicie swapped no começo de cada passada; uma troca em uma passada anterior não informa se a passada atual moveu algum elemento.

Após cada passada, mais uma posição à direita está em sua forma final. Uma passada sem trocas prova que todos os vizinhos comparados estão em ordem. O sufixo já posicionado também está em ordem, portanto o algoritmo pode parar. A passada de confirmação ainda conta como trabalho.

Compare o melhor e o pior caso

Para uma lista ordenada não vazia, a versão com parada antecipada faz $n-1$ comparações e zero trocas. Em uma lista de elementos distintos em ordem inversa, ela faz

comparações e o mesmo número de trocas. Cinco elementos precisam de 10; 1.000 elementos precisam de 499.500. Sem a parada antecipada, o exemplo resolvido de cinco elementos também executaria sua passada final de uma comparação, chegando a 10 comparações.

Cada troca remove exatamente uma inversão. As quatro inversões na lista original do exemplo explicam suas quatro trocas. Vizinhos iguais permanecem no lugar porque o teste usa >, tornando esta versão estável e no próprio local. Substituir > por >= pode inverter registros com chaves iguais.

A posição importa mesmo quando há poucas inversões. [5, 1, 2, 3, 4] usa quatro trocas e uma segunda passada para confirmar a ordem, totalizando sete comparações. [2, 3, 4, 5, 1] também precisa de quatro trocas, mas seu 1 só pode se mover uma vez para a esquerda por passada. Ela precisa de todas as quatro passadas e 10 comparações.

A ordenação por seleção constrói um prefixo ordenado à esquerda. Cada passada encontra o menor elemento no sufixo restante e depois o troca para a próxima posição do prefixo. A varredura encontra a posição; a troca ocorre após a varredura.

Guarde um índice

Na posição i, comece com smallest = i. Compare cada elemento posterior com items[smallest]. Atualize smallest apenas quando aparecer um elemento menor. Quando a varredura terminar, troque items[i] e 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 apenas o menor valor deixaria você sem sua posição para a troca. Começar a varredura no índice 0 revisitaria os elementos já posicionados; a busca restante começa logo depois de i.

Rastreie as passadas

Comece com [29, 10, 14, 37, 13].

O terceiro mínimo já está em sua posição, portanto nenhum valor se move. Após quatro passadas, o último elemento deve ser o maior; ele não precisa de uma passada separada. São 10 comparações e três trocas que movem elementos. A condição no código ignora trocas de uma posição com ela mesma; omitir essa condição deixa o resultado inalterado.

Comparações e trocas têm custos diferentes

A ordenação por seleção sempre faz $n(n-1)\mathrm{/}2$ comparações de elementos: cada passada deve inspecionar todo o sufixo restante para identificar seu mínimo. O total é 10 para cinco elementos ou 499.500 para 1.000, mesmo com entrada já ordenada. Uma varredura que não altera o índice guardado determina o mínimo daquela passada, mas não garante, em geral, que o sufixo restante esteja ordenado.

Para uma lista não vazia, há no máximo uma troca que move elementos por passada, portanto no máximo $n-1$ no total. Uma entrada vazia não precisa de passadas nem de trocas. A ordenação por bolha pode precisar de $n(n-1)\mathrm{/}2$ trocas em uma lista de elementos distintos em ordem inversa. Se mover registros grandes custa muito mais que comparar suas chaves, a pequena contagem de trocas da ordenação por seleção pode ser relevante apesar de suas muitas comparações. Trocar sempre que um novo mínimo aparece durante a varredura elimina essa vantagem.

Chaves iguais podem mudar de ordem

Esse método baseado em trocas funciona no próprio local, mas é instável. Identifique registros de chaves iguais como 4a e 4b para que sua identidade fique visível. Começando com [4a, 4b, 1], a primeira passada troca 4a e 1, produzindo [1, 4b, 4a]. As chaves iguais inverteram sua ordem original, embora o algoritmo nunca as tenha comparado diretamente como diferentes. Manter o primeiro mínimo encontrado durante uma varredura não impede que uma troca entre posições distantes ultrapasse um registro de mesma chave.

A intercalação combina duas listas já ordenadas em uma única saída ordenada. Mantenha um marcador de posição no primeiro elemento ainda não utilizado de cada entrada. Compare esses dois elementos à frente, copie o menor e avance apenas seu marcador.

Escolha o próximo menor elemento

Intercale [3, 27, 38, 43] com [9, 10, 82]:

A lista da esquerda está agora vazia. Copie o 82 restante sem outra comparação de elementos. O resultado é [3, 9, 10, 27, 38, 43, 82], usando seis comparações. Copiar o trecho restante faz parte do algoritmo: parar quando as comparações terminam faria perder dados.

Por que o método pode ignorar os elementos atrás dos que estão à frente? Cada elemento à frente é o menor elemento restante de sua própria lista. O menor deles é, portanto, o menor elemento restante no conjunto. Esse raciocínio continua válido após cada avanço de marcador porque as partes não utilizadas permanecem ordenadas.

Leia o código de intercalação

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 acrescenta um elemento. Uma fatia como left[i:] contém o trecho restante não utilizado, e extend copia seus elementos. Apenas um trecho restante não utilizado pode ser não vazio quando o laço termina. Se uma entrada começar vazia, o laço faz zero comparações e a outra lista é copiada intacta.

Conte comparações e armazenamento

Para duas listas não vazias de comprimentos $m$ e $k$, são necessárias no máximo $m+k-1$ comparações dos elementos à frente. Cada comparação posiciona um elemento, e pelo menos o último elemento pode ser copiado sem comparação. A menor contagem possível de comparações na intercalação é o comprimento da lista menor: [1, 2, 3] intercalada com [4, 5, 6] usa três comparações antes que o lado esquerdo se esgote.

O trabalho total de cópia cresce com $m+k$ mesmo quando as comparações terminam cedo, pois cada elemento deve aparecer na saída. A nova lista também precisa de espaço para $m+k$ elementos. A contagem de comparações, o trabalho de cópia e o armazenamento extra medem partes diferentes da mesma operação.

Trate empates e a ordem das entradas

O teste <= escolhe o elemento da esquerda quando as chaves são iguais. Se as duas entradas vieram de partes consecutivas de uma lista original, isso preserva o registro anterior antes do registro posterior de mesma chave. Essa é a regra de desempate necessária para uma ordenação por intercalação estável.

O requisito de entradas ordenadas é obrigatório. Intercalar [5, 1] com [3] copia 3 e depois o trecho restante [5, 1], produzindo [3, 5, 1]. A regra dos elementos à frente falhou porque 5 não era o menor valor restante em sua própria entrada.

A ordenação por intercalação resolve uma tarefa grande de ordenação dividindo-a em tarefas menores. Isso é divisão e conquista: divida a lista, ordene cada metade e intercale as metades ordenadas.

Pare a divisão no caso base

Uma função é recursiva quando chama a si mesma. A ordenação por intercalação chama a si mesma com listas menores. Seu caso base retorna uma lista de zero ou um elemento sem alteração, pois essa lista já 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)

As fatias dividem a entrada sem perder elementos. Para um comprimento ímpar, o lado direito tem um elemento a mais: [6, 2, 9, 4, 1, 7, 3] é dividida em [6, 2, 9] e [4, 1, 7, 3]. Ambas as metades são menores, portanto as chamadas recursivas acabam chegando ao caso base. Um caso base, por si só, não garantiria a terminação se uma chamada continuasse passando a lista original para si mesma.

Reconstrua a lista ordenada

Rastreie [38, 27, 43, 3, 9, 82, 10, 15]. Ela é dividida em duas metades de quatro elementos, depois em quatro partes de dois elementos e depois em elementos individuais. A divisão não reorganiza os valores. A ordem é construída durante as intercalações:

1. Intercale elementos individuais em [27, 38], [3, 43], [9, 82] e [10, 15]. Cada intercalação usa uma comparação: quatro no total.
2. Intercale pares em [3, 27, 38, 43] e [9, 10, 15, 82]. Cada intercalação usa três comparações: seis no total.
3. Intercale essas metades em [3, 9, 10, 15, 27, 38, 43, 82]. Isso usa sete comparações.

A ordenação completa usa $4+6+7=17$ comparações de elementos. Não conte apenas a intercalação final: as metades ordenadas precisaram ser produzidas primeiro. O exemplo de sete elementos acima é ordenado como [1, 2, 3, 4, 6, 7, 9] usando 14 comparações com essa regra de divisão.

Conte níveis e trabalho por nível

Para oito elementos, a divisão pela metade chega a elementos individuais após três níveis porque $2^3=8$. Em geral, há cerca de ${\log }_{2}n$ níveis de intercalação. Em um nível completo, as intercalações processam coletivamente todos os $n$ elementos. Cada nível, portanto, realiza trabalho proporcional a $n$, levando a um crescimento como $n{\log }_{2}n$.

Para oito elementos, $n{\log }_{2}n=24$ é um limite superior aproximado útil para comparações, não a contagem exata. A lista do exemplo usou 17; uma lista de oito elementos já ordenada ou em ordem inversa usa 12. A ordem da entrada altera o momento em que uma intercalação esgota um lado, mas toda lista ainda passa pelos níveis de divisão e intercalação. O crescimento das comparações permanece $n\log n$ nos melhores e piores casos para esta versão.

Para um milhão de elementos, cerca de 20 níveis dão cerca de 20 milhões de comparações como estimativa de limite superior. A ordenação por seleção usa cerca de 500 bilhões. A diferença cresce rapidamente com o tamanho da entrada.

Considere o espaço extra para a saída

A ordenação por intercalação comum, baseada em listas, precisa de armazenamento extra proporcional a $n$. Escolher o elemento da esquerda nos empates a torna estável.

Um tempo de execução medido depende da máquina e do programa. Uma contagem de passos descreve o trabalho do algoritmo usando uma operação repetida escolhida. O tamanho da entrada, representado por $n$, é o número de elementos processados.

Escolha a operação antes de contar

Para busca e ordenação, as comparações entre valores dos elementos costumam ser uma operação básica útil. Conte as trocas separadamente quando a movimentação dos dados for relevante. Para a busca binária, é conveniente contar as verificações de um elemento central. Na versão em Python, uma verificação central sem sucesso avalia tanto a igualdade quanto a relação de menor que, portanto pode envolver duas comparações de elementos.

Essas contagens descrevem operações repetidas, não linhas de código. Uma linha dentro de um laço pode ser executada um milhão de vezes; várias linhas de preparação podem ser executadas uma vez cada.

Distinga casos do mesmo tamanho

O melhor caso exige o menor número de passos entre as entradas válidas de tamanho $n$. O pior caso exige o maior número e fornece uma garantia. O caso médio calcula a média segundo um padrão declarado de entradas.

Para uma lista não vazia, a busca linear precisa de uma comparação se o valor procurado estiver no início e de $n$ se estiver no fim ou ausente. Sua média para buscas bem-sucedidas é $(n+1)\mathrm{/}2$ quando a primeira posição correspondente tem a mesma probabilidade de ser qualquer posição. A palavra “média” exige essa distribuição; ela não significa o ponto médio entre as contagens do melhor e do pior caso para todo algoritmo.

Transforme laços em contagens

Uma comparação por elemento em uma varredura completa dá $n$ comparações. Dois laços aninhados completos, cada um executado $n$ vezes, executam seu corpo compartilhado $n^2$ vezes. Outro padrão de laços aninhados compara cada par apenas uma vez:

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

A primeira iteração externa compara seu elemento com $n-1$ elementos posteriores. A seguinte compara com $n-2$, e a última não compara com nenhum. O total é

Escreva a soma em ordem direta e inversa. Cada par alinhado soma $n$, e há $n-1$ desses pares. Seu total é $n(n-1)$, o dobro da soma original. Para cinco elementos, $4+3+2+1=10$; para 1.000, a contagem de pares é 499.500.

Reconheça divisões sucessivas pela metade

Um laço que reduz seu trabalho restante pela metade leva cerca de ${\log }_{2}n$ repetições. Um milhão chega pela primeira vez a 1 ou menos após 20 divisões pela metade: $2^{19}=524.288$ é menor que um milhão e $2^{20}=\mathrm{1.048.576}$ é maior. Isso é bem diferente de remover apenas um elemento a cada vez.

Para comparar o crescimento, mantenha o termo de crescimento mais rápido. A contagem de pares é $n^2\mathrm{/}2-n\mathrm{/}2$. Para $n=1.000$, seus termos são 500.000 e 500, portanto o termo quadrático determina o crescimento. Deixar de lado o termo menor e o fator constante descreve a família de crescimento; isso não transforma a contagem exata de 499.500 em uma contagem exata de um milhão.

Uma taxa de crescimento descreve como a quantidade de trabalho muda à medida que a entrada aumenta. Ela ajuda a comparar algoritmos além do tamanho específico usado em um rastreamento.

Conheça as famílias comuns

No crescimento exponencial, acrescentar apenas um elemento já dobra a contagem: $2^{n+1}=2\times 2^n$. Dobrar a entrada é uma mudança muito maior do que acrescentar um elemento.

Compare tamanhos numericamente

Para entradas de 10, 100, 1.000 e um milhão de elementos, ${\log }_{2}n$ é aproximadamente 3,3, 6,6, 10 e 20. Os valores correspondentes de $n{\log }_{2}n$ são aproximadamente 33, 664, 9.966 e 20 milhões. Os valores quadráticos são 100, 10.000, um milhão e um trilhão.

O crescimento logarítmico não é “metade da lista”. Para um milhão de elementos, dividir repetidamente pela metade leva apenas cerca de 20 etapas. Quando a entrada aumenta de 1.000 para 2.000, $n{\log }_{2}n$ aumenta de cerca de 9.966 para 21.932, um fator de cerca de 2,2. O logaritmo também muda, portanto a contagem cresce um pouco mais rápido que a linear.

O trabalho exponencial cresce rapidamente. $2^{10}=1.024$ e $2^{20}$ é cerca de um milhão. A um bilhão de passos por segundo, $2^{50}$ passos ainda levam cerca de 13 dias. Acrescentar mais um elemento dobra esse tempo.

Use a notação O informal

Programadores geralmente identificam essas famílias como $O(1)$, $O(\log n)$, $O(n)$, $O(n\log n)$, $O(n^2)$ e $O(2^n)$. Aqui, elas identificam a família usual de crescimento no pior caso. Leia $O(n^2)$ como “ordem de n ao quadrado”. A notação omite fatores constantes e termos de ordem inferior: $n(n-1)\mathrm{/}2$ comparações pertencem à família quadrática.

Uma notação O não é um tempo de execução exato nem um número de segundos. Ela também não afirma que toda entrada usa a contagem do pior caso. A ordenação por bolha com parada antecipada tem um melhor caso linear, mas um pior caso quadrático.

Encontre o ponto de cruzamento

Suponha que o método A leve $100n$ passos e o método B leve $n^2$. Para 50 elementos, A leva 5.000 passos e B leva 2.500. Para 100, ambos levam 10.000. Para 1.000, A leva 100.000 e B leva um milhão. O crescimento mais lento de A acaba superando seu fator constante maior.

A velocidade do hardware muda a escala sem mudar a família. Um computador 100 vezes mais rápido permite que um método quadrático processe apenas 10 vezes mais elementos no mesmo tempo, pois $(10n{)}^2=100n^2$. Um método linear poderia processar 100 vezes mais. Para uma tarefa pequena, a preparação e as constantes podem predominar; para entradas grandes, o crescimento se torna decisivo.

Um tempo de execução conhecido e um padrão de crescimento permitem prever como uma tarefa maior se comportará. A previsão é uma estimativa porque o tempo real também depende da implementação, da memória, do hardware e de outros trabalhos na máquina.

Ajuste a entrada e depois o tempo

Para trabalho linear, multiplique o tempo pela razão entre os tamanhos das entradas. Se uma busca no pior caso em um milhão de elementos leva 3 milissegundos, dez milhões de elementos levam cerca de 30 milissegundos em condições comparáveis.

Para trabalho quadrático, eleve a razão ao quadrado. Suponha que a ordenação por seleção leve 2 segundos para 50.000 elementos. Dobrar para 100.000 elementos resulta em

segundos. Aumentar para 500.000 elementos multiplica o tamanho da entrada por 10, portanto a estimativa de tempo é de $2\times {10}^2=200$ segundos. Multiplicar o tempo por 10 trataria incorretamente o algoritmo como linear.

Para crescimento $n{\log }_{2}n$, use a razão entre as duas expressões completas. Dobrar uma entrada grande custa um pouco mais que o dobro porque o logaritmo aumenta junto com a contagem de elementos.

Trabalhe em sentido inverso a partir de um limite de tempo

Use o mesmo tempo quadrático de referência: 2 segundos para 50.000 elementos. Um limite de 32 segundos permite 16 vezes o tempo. A entrada pode crescer pela raiz quadrada de 16, que é 4, chegando a cerca de 200.000 elementos. Verifique a relação por substituição: quatro vezes a entrada prevê 16 vezes o tempo, passando de 2 segundos para 32 segundos.

Compare algoritmos em um tamanho grande

Para um milhão de elementos, a ordenação por seleção faz 499.999.500.000 comparações, cerca de 500 bilhões. A ordenação por intercalação precisa de no máximo cerca de 20 milhões. A uma taxa hipotética de um bilhão de comparações por segundo, essas contagens correspondem a cerca de 500 segundos contra 0,02 segundos, uma diferença de aproximadamente 25.000 vezes. Esse cálculo usa o mesmo custo por comparação para isolar o efeito do algoritmo; programas medidos também têm custos de movimentação e acesso à memória.

Teste uma previsão de crescimento

Meça o tempo do mesmo programa em vários tamanhos que dobram, como 10.000, 20.000 e 40.000 elementos. Divida cada tempo pelo anterior. Razões próximas de 2 sugerem crescimento linear; um pouco acima de 2 sugere $n\log n$; próximas de 4 sugerem crescimento quadrático.

Mantenha a máquina e o método de medição consistentes. Repita as execuções e use tamanhos grandes o suficiente para que o tempo de inicialização não predomine. Compare casos semelhantes: buscar na primeira posição em um tamanho e fazer uma busca sem sucesso em outro misturaria os efeitos da entrada com o crescimento. Para a ordenação por bolha, listas ordenadas e listas em ordem inversa precisam de identificações de caso diferentes.

Se tamanhos que dobram resultarem em 0,04, 0,16 e 0,64 segundos, ambas as razões serão 4, apoiando um modelo quadrático nesse intervalo. Uma única razão sujeita a ruído é uma evidência mais fraca que um padrão repetido. Contagens de passos para um rastreamento específico podem ser exatas; uma previsão em segundos deve usar “cerca de” e ser verificada por medições.

Um algoritmo correto para em toda entrada válida e produz a saída exigida. Uma especificação estabelece a condição da entrada e o resultado prometido. Para a busca binária, a pré-condição é a ordem crescente. A pós-condição é um índice correspondente ou -1 exatamente quando o valor procurado está ausente.

Use um invariante para conectar os passos

Um invariante de laço é uma afirmação que vale antes do início do laço e é preservada por cada repetição. Um argumento de correção verifica seu início, sua preservação e o que ele implica quando o laço termina. Separadamente, um argumento de terminação mostra que o laço acaba terminando.

Para a ordenação por seleção, use este invariante: antes da passada i, as primeiras i posições contêm os i menores elementos em ordem.

1. Início: antes da passada 0, o prefixo está vazio. Ele já satisfaz a afirmação.
2. Preservação: a passada encontra o menor elemento restante. Colocá-lo em seguida estende o prefixo ordenado em um elemento, e esse elemento é pelo menos tão grande quanto cada elemento posicionado anteriormente.
3. Fim: após no máximo $n-1$ passadas, apenas o maior elemento permanece fora do prefixo. Toda a lista está ordenada.

Cada movimentação é uma troca, portanto o multiconjunto de elementos também permanece inalterado. Uma saída em ordem, por si só, não atenderia à especificação completa da ordenação.

A ordenação por bolha usa um invariante de sufixo: após $k$ passadas, as últimas $k$ posições contêm os $k$ maiores elementos em ordem. A passada seguinte leva o maior elemento não ordenado até esse sufixo. Uma passada sem trocas estabelece a ordem em toda a parte restante, permitindo a terminação antecipada.

Explique os intervalos descartados pela busca binária

Use o invariante: se o valor procurado aparece, pelo menos uma ocorrência está dentro do intervalo inclusivo de low a high. Inicialmente, esse intervalo cobre toda a lista. Se o valor central for pequeno demais, a ordem da lista torna pequeno demais todo valor em mid ou à sua esquerda. Atualizar low para mid + 1 preserva todas as correspondências possíveis. A atualização para high = mid - 1 segue o mesmo raciocínio para valores grandes demais.

Quando há uma correspondência, a posição retornada atende diretamente à pós-condição. Se o intervalo se esvaziar, o invariante descarta a presença do valor procurado em qualquer lugar da lista. A entrada permanece ordenada porque a busca nunca a altera.

Mostre por que a execução para

Uma medida inteira não negativa que diminui prova o progresso em direção ao fim. Na busca binária, o número de posições candidatas diminui estritamente após cada não correspondência. A posição central testada é excluída, portanto o laço não pode manter o mesmo intervalo para sempre. A ordenação por bolha e a por seleção fazem no máximo $n-1$ passadas em uma entrada não vazia e nenhuma passada em uma entrada vazia.

A ordenação por intercalação chega a listas de zero ou um elemento porque cada chamada recursiva usa uma lista menor. Esses casos base estão ordenados. Supondo que as chamadas menores retornem metades ordenadas corretamente, a intercalação escolhe repetidamente o menor elemento restante e preserva todos os elementos. Isso leva a correção de volta até a chamada original.

Use testes para outra finalidade

Um teste compara um resultado real com um resultado esperado. Passar em muitos testes selecionados aumenta a confiança, enquanto uma única entrada válida que falha é um contraexemplo que refuta a correção. Um argumento geral com invariante cobre a família ilimitada de entradas possíveis que uma coleção finita de testes de exemplo deixa sem verificar. Os testes são especialmente úteis para verificar se o código real implementa o método usado no argumento.

Um caso-limite é uma entrada válida próxima de um limite em que é fácil errar suposições e limites de laço. Planeje o resultado esperado com base na especificação antes de executar o código. Caso contrário, a saída errada de um programa pode se tornar discretamente sua resposta esperada.

Escolha listas que exercitem os limites

Teste listas vazias, de um elemento e de dois elementos; listas já ordenadas e em ordem inversa; valores repetidos e todos iguais; números negativos; e comprimentos ímpares e pares. Para buscas, inclua a primeira posição, a última posição e valores procurados ausentes abaixo, acima e entre os valores armazenados.

Uma busca binária vazia deve retornar -1 sem acessar um elemento: low = 0 e high = -1 tornam o intervalo inicial vazio. Ordenar [3, 3, 3] deve retornar três cópias de 3. Uma saída [3] estaria ordenada, mas não preservaria os elementos.

Rastreie a menor falha

Uma busca binária que usa while low < high não entra no laço para [5] com valor procurado 5. A correção é low <= high, pois um intervalo de uma posição ainda contém um candidato. Esse teste com um elemento isola o limite mais claramente que uma lista longa.

Com low = mid, buscar 20 em [10, 20] define a posição central como 0, vê 10 e deixa low em 0. O intervalo permanece inalterado na repetição seguinte. Use low = mid + 1 para excluir uma posição já verificada. Uma lista de dois elementos com o valor procurado no fim revela esse laço infinito.

A ordenação por bolha compara items[j] com items[j + 1]. Na primeira passada, o último índice válido à esquerda é n - 2. Continuar até n - 1 acessa uma posição além da lista e provoca o IndexError do Python. Esse erro de uma posição no limite é chamado de erro de uma unidade.

Verifique as duas garantias da saída

Para uma ordenação, verifique a ordem dos elementos adjacentes e a contagem de cada elemento original. Use registros identificados para testar a estabilidade. Ana 85, Ben 92, Cara 85 deve manter Ana antes de Cara quando uma ordenação estável por nota agrupa as notas iguais. Uma verificação apenas das notas não perceberia uma troca desses dois registros.

Gere listas aleatórias também. Compare seus resultados com uma implementação confiável, como sorted do Python. Mantenha duplicatas e comprimentos diferentes nas entradas geradas. Quando um teste falhar, reduza a entrada preservando a falha e depois rastreie-a manualmente. Mantenha o pequeno exemplo como teste de regressão para que o erro corrigido continue detectável.

Mantenha segura a aritmética da posição central

Os inteiros do Python crescem conforme necessário, portanto (low + high) // 2 não causa estouro. Algumas linguagens usam inteiros de largura fixa. Para índices não negativos muito grandes, sua soma pode ultrapassar a faixa armazenável. A soma de inteiros em Java retorna ciclicamente; o estouro de inteiro com sinal em C tem comportamento indefinido.

Com índices válidos e low <= high, calcule low + (high - low) // 2. A diferença é não negativa, e o resultado permanece entre os extremos. Isso calcula a mesma posição central arredondada para baixo sem formar a soma que poderia causar estouro. O teste de limites e o raciocínio sobre a representação numérica da linguagem trabalham juntos aqui.

Um algoritmo é adequado a uma tarefa quando seus requisitos e custos correspondem aos dados e ao trabalho realizado. Considere a ordem da entrada, o acesso às posições, o número de operações futuras, a memória extra, a estabilidade e o custo de movimentar registros.

Compare os métodos

A busca binária também precisa de ordem e acesso rápido ao meio. Uma boa comparação inclui esses pré-requisitos; uma contagem pequena de buscas, por si só, deixa de fora o custo de preparar dados inadequados.

Decida se compensa ordenar primeiro

Para uma busca em um milhão de elementos não ordenados, a busca linear custa no máximo um milhão de comparações. Ordenar primeiro por intercalação custa cerca de 20 milhões de comparações antes da primeira busca binária, que então precisa de no máximo 20 verificações centrais. A preparação supera a economia nessa única consulta.

Para 100 consultas em uma lista inalterada, buscas lineares repetidas podem custar 100 milhões de comparações. Ordenar uma vez e fazer 100 buscas binárias custa cerca de 20 milhões de comparações mais 2.000 verificações centrais. A preparação é reutilizada, tornando o segundo plano atraente. Nesse modelo aproximado de custo, o ponto de equilíbrio é de cerca de 20 buscas. A estimativa depende de custos comparáveis das operações e de varreduras no pior caso; não é um limite universal de consultas.

Pondere ordem, movimentação e memória

A ordenação por bolha pode terminar rapidamente quando apenas um par próximo está fora de lugar. [1, 2, 4, 3, 5] precisa de uma troca na primeira passada e de uma segunda passada para confirmar a ordem: sete comparações. Mas “quase ordenada” não garante poucas passadas. Um valor pequeno na extrema direita só pode se mover uma posição para a esquerda a cada passada.

As poucas trocas da ordenação por seleção ajudam quando é custoso mover registros. Tanto a ordenação por seleção quanto a por bolha usam apenas uma quantidade fixa de armazenamento extra. A ordenação por intercalação processa listas grandes com crescimento de tempo muito mais lento, mas sua forma usual baseada em listas precisa de espaço para aproximadamente mais uma lista de elementos.

Se registros com chaves iguais precisarem manter uma ordem anterior, escolha um método estável. Uma lista já em ordem alfabética por nome pode ser ordenada de forma estável por nota, permanecendo em ordem alfabética dentro de cada grupo de notas. A ordenação por seleção comum pode alterar a ordem desses empates.

Use ferramentas de biblioteca testadas

Programas reais geralmente usam a ordenação integrada da linguagem. A ordenação estável do Python usa um método adaptativo baseado em intercalação, geralmente chamado Timsort, que se beneficia da ordem já presente na entrada. sorted(items) retorna uma nova lista, enquanto items.sort() altera a lista existente. Um método que altera uma lista no próprio local como comportamento de sua API ainda pode usar memória de trabalho temporária internamente; ele não precisa satisfazer a definição de armazenamento extra fixo usada para as ordenações simples acima.

Para poucos elementos, um código simples e claro pode importar mais que o crescimento. Para coleções grandes, compare o comportamento no pior caso e a memória junto com as propriedades que a tarefa realmente exige.