Inserir classificação
Classificação por inserção (Classificação por inserção) — ;algoritmo de classificação no qual os elementos da sequência de entrada são pesquisados um de cada vez, e cada novo elemento de entrada é colocado no local apropriado entre os elementos classificados anteriormente.
Inserir classificação – é um algoritmo muito simples, mas ineficiente que, no entanto, possui várias vantagens específicas que o tornam relevante mesmo depois que muitos outros algoritmos geralmente mais eficientes foram desenvolvidos.
Com a classificação por inserção, você não precisa ter todo o array na frente antes de classificar. O algoritmo pode receber um elemento por vez durante a classificação. Isso é muito útil se precisarmos adicionar mais elementos durante a classificação. O algoritmo irá inserir o novo elemento no lugar certo sem "reexecutar" classificando toda a matriz.
A classificação por inserção pode ser usada na prática devido à sua eficiência em conjuntos de dados pequenos (~10 elementos).
O problema é o seguinte: existe uma parte do array que já está ordenada, e você quer inserir os demais elementos do array na parte ordenada, mantendo a ordem. Para fazer isso, a cada passo do algoritmo, selecionamos um dos elementos de dados de entrada e o inserimos na posição desejada na parte já ordenada do array, até que todo o conjunto de dados de entrada esteja ordenado. O método de selecionar o próximo elemento da matriz de entrada é arbitrário, mas geralmente (e para obter um algoritmo de classificação estável), os elementos são inseridos na ordem em que aparecem na matriz de entrada.
Implementação algorítmica deste algoritmo
// O elemento nulo é considerado uma sequência já classificada.
// Portanto, o loop começa em 1
LOOP PARA I=1 PARA N-1 PASSO 1
X=A[I]
J=eu
WHEN J>0 AND A[J-1]>X //procurando um lugar para inserir
TROCA A[J],A[J-1]
J=J-1
Tchau
A[J]=X
PROXIMO EU
Complexidade computacional: \(\displaystyle O(n^{2})\).