Conteúdo[Esconder][Mostrar]
A ciência da computação tem tudo a ver com a compreensão das complexidades dos algoritmos e estruturas de dados.
Você tem uma lista de itens que precisam ser classificados, mas não tem tempo ou recursos para usar um algoritmo de classificação mais complexo.
A ordenação por inserção é um dos algoritmos de ordenação mais simples, mas pode ser lenta para listas grandes.
Fácil implementação e compreensão tornaram este método um favorito entre os programadores. É perfeito para pequenas listas ou quando você precisa de uma solução rápida.
Nesta postagem do blog, veremos a complexidade de tempo da classificação por inserção. Este algoritmo é usado para ordenar arrays e tem um tempo de execução de O(n2). Isso significa que a complexidade de tempo aumenta com o tamanho do array.
No entanto, esse algoritmo pode ser mais rápido do que outros algoritmos de classificação, como o quicksort.
Vamos dar uma olhada em como funciona a classificação por inserção!
O que é algoritmo de ordenação por inserção?
Um elemento de cada vez, a ordenação por inserção gera um array classificável, que é frequentemente denominado como uma lista.
Por exemplo, a classificação é aplicada em programas de computador complicados, como compiladores, onde a ordem dos tokens é importante para a interpretação do programa.
Como funciona a classificação por inserção?
Quando usamos a ordenação por inserção para ordenar um array, o algoritmo começa encontrando o menor item da lista e inserindo-o na posição correta.
Em seguida, ele encontra o próximo item menor e o insere na posição correta e assim por diante.
O algoritmo funciona percorrendo a lista, comparando cada item com o que vem antes dele.
Se os itens estiverem na ordem errada, o algoritmo os troca. Em seguida, ele verifica se a lista está classificada e, se estiver, o algoritmo termina.
Na prática, a ordenação por inserção é frequentemente implementada usando algumas linhas de código, tornando-se uma escolha popular para ordenar pequenos arrays. No entanto, a complexidade do tempo deve ser considerada ao usar este algoritmo.
Exemplo:
Aqui está um exemplo de como funciona a classificação por inserção. Usaremos a seguinte matriz:
1, 2, 3, 4, 5, 6
O algoritmo começa encontrando o menor item da lista, que é 1. Em seguida, ele o insere na posição correta, a primeira posição. Em seguida, ele encontra o próximo item menor, que é 2. Ele o insere na posição correta, que é a segunda posição.
Em seguida, ele encontra o próximo item menor, que é 3. Ele o insere na posição correta, que é a terceira posição.
Em seguida, ele encontra o próximo item menor, que é 4. Ele o insere na posição correta, que é a quarta posição, e assim por diante. A lista já está ordenada!
Podemos ver pelo exemplo que o algoritmo faz seis comparações e trocas para classificar a lista. Isso porque leva n2 comparações e trocas para classificar uma lista de n itens. Neste caso, n=6.
Como melhorar a complexidade do tempo de classificação de inserção?
Enquanto a ordenação por inserção tem um tempo de execução de O(n2), ele pode ser melhorado usando um algoritmo de ordenação melhor, como quicksort.
Quicksort tem um tempo de execução O(n log n), que é muito mais rápido que O(n)2).
No entanto, em alguns casos, a classificação por inserção pode ser mais rápida que a classificação rápida.
Por exemplo, se a lista já estiver em ordem, a classificação por inserção levará menos tempo do que a classificação rápida.
Na prática, a ordenação por inserção é frequentemente implementada usando algumas linhas de código, tornando-se uma escolha popular para ordenar pequenos arrays.
No entanto, a complexidade do tempo deve ser considerada ao usar este algoritmo.
Complexidades de tempo
Complexidade de pior caso O(n2):
A complexidade de tempo aumenta com o tamanho do array. leva n2 comparações e trocas para classificar uma lista de n itens.
Por exemplo, se tivermos uma matriz de tamanho 1000, o algoritmo fará 1,000,000 de comparações e trocas para classificar a matriz.
Complexidade do melhor caso O(n):
A complexidade de tempo é igual ao tamanho da matriz de entrada. eu
t leva n comparações e trocas para classificar uma lista de n itens. Por exemplo, considere uma matriz de tamanho 5. O algoritmo fará cinco comparações e trocas para classificar a matriz.
Complexidade Média de Caso O(n2):
A complexidade de tempo está entre as complexidades de pior e melhor caso neste caso.
leva n2 comparações e trocas para classificar uma lista de n itens.
Assim, a ordenação por inserção é um algoritmo de ordenação estável.
Por que a classificação por inserção é estável?
A ordenação por inserção é estável porque preserva a ordem dos elementos iguais na matriz de entrada.
Isso é importante para muitos aplicativos, como recuperação de dados ou análise financeira. Por exemplo, se temos duas listas de números e queremos compará-las, precisamos garantir que a ordem dos elementos seja preservada.
Se as listas não estiverem ordenadas, não as compararemos com precisão.
Deixe um comentário