Classificação de inserção em JavaScript
O algoritmo de classificação de inserção é muito útil nos casos em que temos um número menor de elementos em uma lista ou onde a maioria da lista já está classificada e menos elementos são extraviados.
Como funciona a classificação da inserção
Vamos considerar um exemplo para entender melhor a lógica por trás do tipo de inserção. Suponha que tenhamos uma matriz não classificada de 6 elementos e temos que classificá -los usando o tipo de inserção:
Agora, para classificar a matriz acima, iremos iterar a matriz do índice 1 para o último índice. Inicialmente, assumimos que o 0º índice da matriz é classificado, depois faremos uma comparação do elemento atual com seu elemento anterior. Se o elemento atual for menor que o elemento anterior, trocaremos suas posições.
Primeiro passo
Na primeira etapa, compararemos o índice 1 com o índice 0, o valor do primeiro índice '47' é maior que 0º valor do índice; portanto, não haverá alteração na primeira etapa (os elementos não trocaram):
Segundo passo
Agora, na segunda etapa, assumiremos que os dois primeiros elementos são classificados, então o cursor estará no índice 2 e compararemos o índice 2 com seus elementos anteriores:
Como '25' é menor que '47', troca '25' e '47'. Em seguida, '25' também é comparado com o valor 0º índice. '25' é maior que '15', então não seria trocado.
A matriz após a segunda etapa será atualizada como:
Terceiro passo
Aqui na terceira etapa, consideramos os três primeiros valores classificados e o cursor estará no terceiro índice. Portanto, compararemos o terceiro índice com seus valores anteriores:
No índice 3, '55' é comparado com cada elemento um por um, mas é maior do que todos os seus elementos anteriores, para que não haja alteração na posição dos elementos da matriz.
Quarta etapa
Agora estamos no índice 4, onde temos um valor '20' e temos que compará -lo com todos os elementos anteriores da matriz:
Como '20' é menor que '25', '47' e '55', para que seja inserido no primeiro índice e '25', '47' e '55' será movido para o lado direito por um índice (I+1 índice) de seus índices atuais.
A matriz atualizada será:
Quinto passo
Agora estamos no índice 5, onde o valor atual é '10', que é o menor entre todos os valores da matriz, por isso será inserido no 0º índice.
Dessa forma, toda a matriz será classificada usando o tipo de inserção:
Como terminamos com a parte conceitual do tipo de inserção, agora implementaremos esse conceito em JavaScript.
Implementação da classificação de inserção em JavaScript
O código para implementar o tipo de inserção em JavaScript é o seguinte:
função insertion_sort (input_array, array_length)
deixe eu, pivot_value, j;
for (i = 1; i = 0 && input_array [j]> pivot_value)
input_array [j + 1] = input_array [j];
j = j - 1;
input_array [j + 1] = pivot_value;
retornar input_array;
deixe input_array = [15,47,25,55,20,10];
Deixe Array_length = input_array.comprimento;
insertion_sort (input_array, array_length);
console.log ("Final classificado Array:", input_array);
No código acima, criamos uma função “insertion_sort”E passou a matriz de entrada e o comprimento da matriz. Então nós iteramos o loop até o comprimento da matriz.
Dentro do loop, selecionamos o 'pivot_value = input_array [i]'Como um valor pivô para fazer uma comparação do elemento atual com seus elementos anteriores e definir “j = i-1”, Que representa o último elemento da nossa matriz classificada.
Aqui em cada iteração, o elemento atual é atribuído ao valor do pivô e o valor do pivô será considerado como o primeiro elemento da matriz não classificada em cada etapa.
Utilizamos um loop de tempo para classificar os elementos da matriz, aqui neste loop, comparamos o elemento atual com seus elementos anteriores. Se o elemento atual for menor do que qualquer um dos elementos anteriores, e encontramos a posição apropriada para inserir esse elemento na matriz classificada, inserimos esse elemento na posição apropriada e movendo os outros elementos um lugar para o lado direito. E todo o fenômeno é repetido para cada etapa até que a matriz seja resolvida completamente.
Saída
Finalmente, chamamos o “insertion_sort”Funciona e imprima a matriz classificada no console do navegador usando o“console.registro”Método. A saída do algoritmo de classificação de inserção será:
Conclusão
O tipo de inserção é um algoritmo de classificação que classifica um elemento de cada vez. Ele insere o elemento na posição apropriada um por um para criar uma matriz classificada. Ele fornece resultados eficientes se o número de elementos da matriz for pequeno e a maioria dos elementos da matriz já for classificada.
Neste artigo, consideramos um exemplo para descobrir a lógica do tipo de inserção, discutimos o funcionamento do algoritmo de classificação de inserção em relação a cada etapa e apresentamos a matriz atualizada após cada etapa. E, finalmente, uma vez que percebemos a ideia por trás do tipo de inserção, então a implementamos em JavaScript.