Introdução à inserção Classificar em JavaScript
A classificação é um dos conceitos importantes que os programadores aprendem a começar sua jornada na ciência da computação, independentemente da linguagem de programação selecionada para aprender. A classificação nos ajuda a localizar os dados de destino que queremos pesquisar de maneira mais rápida e conveniente, classificando-os em ordem crescente ou decrescente.
Os algoritmos de classificação são usados para reordenar elementos, onde um elemento pode ser um número ou uma sequência. Existem muitos tipos de algoritmos de classificação com base no método de classificação e na abordagem que eles seguem para classificar os elementos, e cada tipo tem suas vantagens e desvantagens.
Neste blog, focaremos na classificação por inserção, uma classificação comum que é fácil de entender e implementar.
O que é a inserção de classificação em JavaScript?
A Classificação de Inserção é um algoritmo simples e fácil de entender, que funciona melhor com uma pequena lista de dados, classificando cada elemento na lista de dados, um por um, da esquerda para a direita. Também é conhecido como uma classificação de comparação, na qual compara o valor atual com os outros valores na mesma lista de dados que está sendo classificada. Segue uma abordagem iterativa para colocar cada elemento na ordem correta na lista de dados.
Quanto mais tempo um algoritmo leva para classificar, seu desempenho é considerado ruim e precisa considerar outro algoritmo para classificar os dados. A classificação por inserção tem uma complexidade de tempo de O (n²) ou executa o tempo quadrático para classificar a lista de dados no pior cenário. Isso normalmente não é muito eficaz e não deve ser usado para listas grandes. No entanto, geralmente supera os algoritmos avançados, como quicksort ou mergesort em listas menores.
Classificação por inserção, na maioria das vezes é mais eficiente do que outros algoritmos de classificação quadrática, como classificação por bolha ou classificação por seleção. Seu melhor cenário, o tempo é O (n) ou linear, o que ocorre se a matriz de entrada já estiver classificada. Em média, o tempo de execução da classificação de inserção ainda é quadrático.
No exemplo abaixo, teremos uma abordagem fácil de alto nível para classificar os dados armazenados em uma estrutura de dados de matriz e usar seu método de classificação para classificar os dados sem implementar algoritmos.
Exemplo - Algoritmo de classificação de inserção
Código:
// Declaring unsorted data and storing it in array data structure
var dataArray = (96, 5, 42, 1, 6, 37, 21) // Function - Insertion Sort Algo.
function insertSort(unsortedData) (
for (let i = 1; i < unsortedData.length; i++) (
let current = unsortedData(i);
let j;
for(j=i-1; j >= 0 && unsortedData(j) > current;j--) (
unsortedData(j + 1) = unsortedData(j) )
unsortedData(j + 1) = current;
)
return unsortedData;
)
// print sorted array
console.log(insertSort(dataArray));
Resultado:
Explicação: No algoritmo, implementamos 2 para loops, o loop for externo é para iterar sobre os elementos da matriz e o loop for interno é usado para classificar os elementos da matriz na ordem crescente de seu valor. A variável atual mantém o valor atual da matriz e a variável j é definida como um valor menor que a posição atual do índice da matriz. Verificamos se o elemento atual (atual) é menor que o valor da matriz na j- ésima posição (unsortedData (j) ) e se é verdadeiro, classificamos esses valores.
Iteração 1 - corrente (96): (96, 5, 42, 1, 6, 37, 21)
Iteração 2 - corrente (5): (5, 96, 42, 1, 6, 37, 21)
Iteração 3 - corrente (42): (5, 42, 96, 1, 6, 37, 21)
Iteração 4 - corrente (1): (1, 5, 42, 96, 6, 37, 21)
Iteração 5 - corrente (6): (1, 5, 6, 42, 96, 37, 21)
Iteração 6 - corrente (37): (1, 5, 6, 37, 42, 96, 21)
Iteração 7 - corrente (21): (1, 5, 6, 21, 37, 42, 96)
A iteração externa do loop for começa na 1ª posição do índice, pois queremos mover o menor elemento para o lado esquerdo, então estamos comparando se o elemento atual é menor que os elementos do lado esquerdo.
Tipos de classificação
Os tipos de algoritmos usados para classificar dados englobam os seguintes conceitos ou idéias em sua abordagem para classificar os dados:
- Estratégias de comparação versus não baseadas em comparação,
- Implementação iterativa versus recursiva,
- Paradigma de dividir e conquistar (isto ou aquilo),
- Abordagem aleatória.
Vamos considerar alguns exemplos:
1. A classificação de mesclagem usa uma abordagem de dividir e conquistar para classificar elementos em uma matriz.
2. Classificação de inserção, Classificação de bolha é uma classificação baseada em comparação.
Quando os dados são classificados, fica mais fácil encontrar uma solução ideal para problemas complexos. por exemplo,
- Procurando por um valor específico,
- Encontrando o valor mínimo ou máximo,
- Teste de exclusividade e exclusão de duplicatas,
- Contando quantas vezes um valor específico apareceu, etc.
Conclusão
Neste artigo, examinamos a definição de classificação por inserção e sua complexidade de tempo e vários outros tipos de algoritmos de classificação com base em sua abordagem. O estudo de vários algoritmos de classificação nos ajuda a identificar qual deles é mais adequado em determinadas circunstâncias ou casos de uso que nos ajudam a classificar os dados em uma taxa mais rápida.
Artigos recomendados
Este é um guia para a Classificação por inserção em JavaScript. Aqui discutimos o que é a classificação por inserção em javascript e seus tipos com exemplo. Você também pode consultar os seguintes artigos para saber mais -
- Padrões em JavaScript
- Declaração de caso em JavaScript
- Instruções condicionais em JavaScript
- Objetos JavaScript
- Diferentes tipos de loops com suas vantagens