Ordenação por inserção
Ordenação por inserção é um experimento interativo de Algoritmos em ação, uma simulação gratuita do StudyFi Lab que funciona direto no navegador.
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?
Perguntas frequentes
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.
Como experimento “Ordenação por inserção”?
Corre-o num vetor quase ordenado e depois num invertido. Quantas vezes mais deslocamentos precisa o invertido?
Estudando para uma prova?
Envie suas anotações e o StudyFi as transforma em flashcards, testes e podcasts.