Em sua essência, o tipo de inserção serve como um algoritmo de classificação. Ele pode colocar vários elementos não classificados nos locais mais adequados para eles a cada iteração. Seria justo dizer que este algoritmo funciona de forma bastante semelhante à forma como as pessoas classificam os cartões em suas mãos. Se você tem experiência em jogos de cartas, você saberá que os jogadores de cartas classificam com a suposição de que as primeiras cartas já estão classificadas, após o que eles selecionam as não classificadas.
Caso a carta não classificada se mostre maior em comparação com a carta na mão dos jogadores, eles têm que colocá-la à direita. Caso contrário, eles têm que manter a carta do lado esquerdo. Da mesma forma, é preciso colocar o resto das cartas não classificadas e mantê-las em seus respectivos lugares. A abordagem utilizada pelo tipo de inserção é bastante semelhante a esta.
Noções básicas de como funciona a ordenação de inserção
Mencionamos a seguir três passos que lhe darão uma visão mais baixa da forma como funciona o tipo de inserção:
- Na primeira etapa, os elementos em questão são comparados com os elementos adjacentes a eles
- Se cada comparação mostra que o elemento em consideração pode ser usado em uma posição específica, então há espaço para isso. Isto é feito movendo a posição de outros elementos para a direita.
- Este procedimento continua até que cada elemento presente na matriz encontre sua posição correta.
Características de ordenação da inserção
Embora este algoritmo de classificação no local tenha uma ampla gama de características, há três importantes com as quais todos devem se familiarizar.
- Primeiro, o algoritmo de classificação de inserção é incrivelmente simples. Alguns até diriam que é o mais simples por aí devido a sua simples implementação.
- Se você é um programador que lida regularmente com pequenos valores de dados, o uso deste algoritmo virá a ser bastante útil
- O algoritmo de classificação de inserção é bastante adaptativo, tornando-o ideal para conjuntos de dados parcialmente classificados
Perguntas mais comuns sobre o tipo de inserção
Aqui está uma lista de respostas concisas a perguntas comuns feitas sobre os algoritmos de ordenação de inserção.
O que são casos de Algoritmos de Ordenação de Inserção?
A ordenação de inserção requer muito tempo quando se trata de ordenação de elementos que estão em ordem inversa. Entretanto, se os elementos já estiverem ordenados, não será necessário muito tempo.
Os Algoritmos de Ordenação de Inserção são Estáveis?
Os algoritmos de classificação de inserção são incrivelmente estáveis, especialmente quando você os compara com outros algoritmos.
Quando é o melhor momento para usar o Algoritmo de classificação de inserção?
Como mencionado anteriormente, o algoritmo de classificação de inserção é freqüentemente utilizado sempre que há uma pequena quantidade de elementos. Dito isto, ele também pode ser bastante útil quando um conjunto de elementos de inserção não precisa de muita ordenação e tem apenas alguns elementos mal colocados.
Que tipo de inserção se segue?
A abordagem seguida pelo algoritmo de classificação de inserção é incremental, e é por isso que ele é incrivelmente popular entre os programadores de classificação de arrays.
Ordenação de Inserção Binária Explicada
Os programadores podem utilizar a busca binária para reduzir a quantidade de comparações presentes no tipo de inserção regular. O tipo de inserção binária faz uso da busca para encontrar o local ideal para a inserção do item escolhido a cada iteração. Quando se trata de inserção regular, a ordenação utiliza O(i) (em iteração) durante o pior cenário.
Podemos usar a pesquisa binária para reduzi-la a isto: O(logi). Dito isto, no entanto, o algoritmo ainda tem um tempo de execução em torno de O(n^2) para os piores casos. Isto se deve à quantidade de swaps necessários por inserção.
Etapas para implementar o Sort de inserção em listas vinculadas
Os passos mencionados abaixo mostram como se pode fazer uso do algoritmo de ordenação de inserção em uma lista vinculada.
- Comece desenvolvendo uma lista ordenada, certificando-se de que ela esteja vazia.
- Atravesse a lista que você criou e siga este passo para cada nó
- Insira o nó atual na forma de resultado ou lista ordenada
- Finalmente, mudar o chefe da lista vinculada, tornando-a chefe da lista ordenada, também conhecida como lista de resultados
As principais aplicações do tipo de inserção
Aqui estão dois dos cenários mais comuns quando os programadores utilizam o tipo de inserção.
– Em primeiro lugar, eles a utilizam sempre que há uma matriz com alguns elementos
– A classificação da inserção também pode ser útil quando há apenas um pequeno número de elementos para classificar.
Complexidades de tempo de inserção
Aqui está um olhar sobre as complexidades de tempo que você poderia encontrar no tipo de inserção.
Pior complexidade de casos O (n2) – Worst Case Complexity O (n2)
Imagine que há uma matriz presente em ordem ascendente, que você planta para ordenar em ordem descendente. Um caso como este resulta na pior das hipóteses em complexidade. Em tal situação, você tem que comparar cada elemento com outros elementos para garantir que haja (n-1) comparações para cada n-ésimo elemento.
A quantidade total de comparações será n*(n-1) ~ n2
Complexidade média de casos O(n) – Average Case Complexity O(n)
Este tipo de complexidade ocorre freqüentemente sempre que os elementos de uma matriz são misturados, o que significa que eles não estão em ordem decrescente ou ascendente.
Complexidade espacial – Space Complexity
A complexidade do espaço torna-se 0(1) sempre que há uma implementação de uma variável extra.
Complexidade do melhor caso – Best Case Complexity
Sempre que um laço não requer nenhuma classificação, a quantidade de vezes que o laço externo funciona é n. Por outro lado, o laço interno permanece inativo e não funciona. Isto significa que a quantidade de comparações será n, resultando em uma complexidade linear.
Análise da Complexidade do Tempo
Embora não se possa negar o quão eficiente é o tipo de inserção, mas se um fornecesse uma matriz que já está classificada, o algoritmo ainda assim realizaria o outro para o laço. Isto exigirá n etapas para ordenar um array dos n elementos que já foram ordenados para começar, essencialmente transformando a melhor complexidade de tempo do caso em uma função n linear.
Uma matriz não classificada requer um elemento para fazer comparações com outros elementos, significando que cada elemento de n é comparado com outros n elementos. Isso também ajudaria a analisar outros algoritmos similares como Quick Sort, Merge Sort ou Selection Sort e medir suas respectivas complexidades.