Algoritmos em ação
Algoritmos em ação é uma simulação interativa gratuita do StudyFi Lab. Funciona direto no navegador, sem cadastro e sem instalar nada.
Ordenar e buscar, passo a passo
Experimentos
Ordenação por bolha
A ordenação por bolha compara elementos vizinhos e troca-os quando estão na ordem errada. Depois de cada passagem, o maior elemento “sobe como uma bolha” até ao fim, por isso a parte por ordenar fica mais curta. Se uma passagem não fizer trocas, o vetor está ordenado. No pior caso precisa de n(n−1)/2 comparações, ou seja, O(n²).
Experimente: Escolhe a entrada invertida e compara as comparações com n(n−1)/2. Depois experimenta um vetor quase ordenado — termina após poucas passagens.
Ordenação por inserção
A ordenação por inserção funciona como ordenar cartas na mão: a parte esquerda já está ordenada e cada novo elemento (key) desloca-se para a esquerda até encontrar um menor. Pelo caminho, os elementos maiores avançam uma posição para a direita. Com dados aleatórios é O(n²), mas com dados quase ordenados é quase O(n) — um vetor ordenado precisa só de n−1 comparações.
Experimente: Corre-o num vetor quase ordenado e depois num invertido. Quantas vezes mais deslocamentos precisa o invertido?
Ordenação por fusão
A ordenação por fusão divide o vetor ao meio, ordena cada metade da mesma maneira (recursão) e depois funde as duas metades ordenadas: escolhe sempre o menor dos dois elementos da frente. Dividir ao meio dá log₂ n níveis e cada nível trata todos os n elementos, por isso o tempo é sempre O(n log n). Em caso de empate escolhe o da esquerda, por isso é estável.
Experimente: Experimenta um vetor invertido e depois um quase ordenado do mesmo tamanho. As comparações quase não mudam — a ordem da entrada pouco importa.
Ordenação rápida
A ordenação rápida escolhe um pivô — aqui o último elemento do intervalo (partição de Lomuto) — e reorganiza o intervalo para que os menores fiquem à esquerda e os restantes à direita. O pivô fica então na sua posição final e as duas partes são ordenadas da mesma forma. Em média é O(n log n), mas quando o pivô divide mal (por exemplo, num vetor já ordenado ou invertido) cai para O(n²).
Experimente: Compara a entrada aleatória com a invertida. No vetor invertido o pivô é sempre o maior ou o menor — vê como as comparações disparam.
Pesquisa linear vs. binária
A pesquisa linear verifica os elementos um a um, por isso no pior caso precisa de n passos — O(n). A pesquisa binária só funciona num vetor ordenado: olha para o meio e, conforme o resultado, descarta uma metade inteira. Depois de cada passo resta no máximo metade, por isso bastam no máximo ⌈log₂(n+1)⌉ passos — O(log n). Para 40 elementos são 6 passos em vez de 40.
Experimente: Define 40 elementos e procura o último valor. Depois escolhe um número que não está no vetor — quantos passos precisa cada pesquisa para o descobrir?
Corrida de ordenações
Os quatro algoritmos ordenam a mesma entrada e, em cada pista, um passo é uma comparação ou um movimento. Os algoritmos O(n²) (bolha e inserção) crescem com o tamanho do vetor muito mais depressa do que os O(n log n) (fusão e rápida). A ordem também depende da entrada: num vetor quase ordenado a inserção ganha muitas vezes.
Experimente: Começa a corrida com um vetor aleatório de 40 elementos e depois muda para quase ordenado. O vencedor muda?
Perguntas frequentes
O que é Algoritmos em ação?
Algoritmos em ação é uma simulação interativa gratuita do StudyFi Lab. Funciona direto no navegador, sem cadastro e sem instalar nada. Ordenar e buscar, passo a passo
Algoritmos em ação é gratuito?
Sim. Algoritmos em ação é totalmente gratuito. Funciona no navegador do computador, tablet ou celular, e você não precisa de conta.
O que posso explorar em Algoritmos em ação?
Ordenação por bolha, Ordenação por inserção, Ordenação por fusão, Ordenação rápida, Pesquisa linear vs. binária, Corrida de ordenações.
O que mostra o experimento “Ordenação por bolha”?
A ordenação por bolha compara elementos vizinhos e troca-os quando estão na ordem errada. Depois de cada passagem, o maior elemento “sobe como uma bolha” até ao fim, por isso a parte por ordenar fica mais curta. Se uma passagem não fizer trocas, o vetor está ordenado. No pior caso precisa de n(n−1)/2 comparações, ou seja, O(n²).
O que mostra o experimento “Ordenação por inserção”?
A ordenação por inserção funciona como ordenar cartas na mão: a parte esquerda já está ordenada e cada novo elemento (key) desloca-se para a esquerda até encontrar um menor. Pelo caminho, os elementos maiores avançam uma posição para a direita. Com dados aleatórios é O(n²), mas com dados quase ordenados é quase O(n) — um vetor ordenado precisa só de n−1 comparações.
Estudando para uma prova?
Envie suas anotações e o StudyFi as transforma em flashcards, testes e podcasts.