Introdução aos algoritmos de classificação em JavaScript

Semelhante à maioria das outras linguagens de programação, você pode encontrar cenários em que é necessário classificar alguns números em JavaScript em ordem crescente ou decrescente. Para fazer isso, podemos usar muitos algoritmos, como classificação de bolhas, classificação de seleção, classificação de mesclagem, classificação rápida, etc. Esses algoritmos não diferem apenas em como eles funcionam, mas também têm demandas diferentes em termos de memória e tempo, vamos aprofunde-se em alguns dos algoritmos de classificação importantes e veja como você pode usá-los no seu código JavaScript.

Os 6 principais algoritmos de classificação em JavaScript

Aqui estão alguns algoritmos de classificação em javascript explicados abaixo com exemplos:

1. Algoritmo de classificação de bolhas

Considerada uma das ferramentas mais comuns desse comércio, a classificação por bolhas funciona criando um loop que compara cada item da matriz com outro item. Se o item comparado for menor que o disponível, trocamos de lugar. Isso continua até que tenhamos um passe em que nenhum item na matriz é maior que o item ao lado.

A classificação por bolhas possui complexidade de tempo O (n 2 ) e complexidade de espaço O (n).

Código:

function swap(arr, firstIndex, secondIndex)(
var temp = arr(firstIndex);
arr(firstIndex) = arr(secondIndex);
arr(secondIndex) = temp;
)
function bubbleSortAlgo(arraaytest)(
var len = arraaytest.length,
i, j, stop;
for (i=0; i < len; i++)(
for (j=0, stop=len-i; j < stop; j++)(
if (arraaytest(j) > arraaytest(j+1))(
swap(arraaytest, j, j+1);
)
)
)return arraaytest;
)
console.log(bubbleSortAlgo((3, 6, 2, 5, -75, 4, 1)));

Resultado:

2. Algoritmo de Classificação da Seleção

Agora que terminamos de discutir o algoritmo de classificação de bolhas, vamos dar uma olhada apenas como um algoritmo popular para classificação chamado Selection Sort.

Ao contrário do Bubble Sort, nos concentramos em encontrar o menor valor na matriz para realizar a classificação. Aqui está um detalhamento passo a passo de como a Classificação da Seleção funciona:

  • Assumimos o primeiro item da matriz como o menor.
  • Comparamos esse item com o próximo item da matriz.
  • Se o próximo item for menor que o disponível, definiremos o próximo item como o novo menor valor.
  • Continuamos repetindo essas etapas até chegar ao final da matriz.
  • Quando encontramos valor na matriz menor do que o que começamos, trocamos suas posições.
  • Continuamos fazendo as comparações e passando para o próximo item. Até a matriz inteira ser classificada.

Assim como o algoritmo Bubble Sort, a classificação Selection tem complexidade de tempo O (n 2 ) e complexidade de espaço O (n).

Código:

function SelectionSortAlgo(array, compare_Function) (
function comp(a, b) (
return a - b;
)
var min = 0;
var index = 0;
var temp = 0;
compare_Function = compare_Function || compare;
for (var i = 0; i < array.length; i += 1) (
index = i;
min = array(i);
for (var j = i + 1; j < array.length; j += 1) (
if (compare_Function(min, array(j)) > 0) (
min = array(j);
index = j;
)
)
temp = array(i);
array(i) = min;
array(index) = temp;
)
return array;
)
console.log(SelectionSortAlgo((9, 15, 2, 44, -1, 36, 1), function(a, b) ( return a - b; )));

Resultado:

3. Algoritmo de classificação de mesclagem

Semelhante ao Bubble Sort e Selection Sort, o Merge sort é um dos algoritmos de classificação mais populares da ciência da computação, você pode implementá-lo na maioria das linguagens de programação e possui bom desempenho sem precisar de recursos.

A Merge Sort usa o método Divide and conquist para classificar uma matriz ou qualquer lista de elementos. O termo divide e conquista significa que dividimos um grande problema em vários problemas menores e depois resolvemos esses pequenos problemas. Uma vez resolvidos os problemas menores, combinamos os resultados que resultam na solução do grande problema.

Na verdade, entender o algoritmo é simples:

  • Dividimos a matriz fornecida em n matrizes, cada uma dessas matrizes contém apenas 1 elemento.
  • Mesclar as matrizes para produzir uma nova matriz.
  • Repita a etapa 2 até que haja apenas 1 matriz restante, que será a matriz classificada.

Código:

function merge_sort_algo(left, right)
(
var i = 0;
var j = 0;
var result = ();
while (i < left.length || j < right.length) (
if (i === left.length) (
// j is the only index left_part
result.push(right(j));
j++;
)
else if (j === right.length || left(i) <= right(j)) (
result.push(left(i));
i++;
) else (
result.push(right(j));
j++;
)
)
return result;
)
console.log(merge_sort_algo((1, 44, 6), (84, 7, 5)));

Resultado:

4. Algoritmo de Classificação Rápida

O Quicksort é uma das maneiras mais eficientes de classificar elementos em sistemas de computador. Para mesclar a classificação, o Quicksort trabalha no algoritmo de dividir e conquistar. Nesse caso, encontramos um item dinâmico na matriz para comparar todos os outros elementos de matriz e, em seguida, movemos os itens de maneira que todos os itens antes dos itens selecionados sejam menores e todos os itens após o item dinâmico tenham um tamanho maior. Depois de fazer isso, a chave é continuar fazendo isso repetidamente e teremos nossa matriz classificada.

A seguir estão as etapas que podem ser seguidas para implementar o algoritmo quicksort:

  • Selecionamos um elemento da matriz e chamamos de "ponto de articulação"
  • Iniciamos um ponteiro chamado ponteiro esquerdo, a partir do qual está o primeiro elemento da matriz.
  • Da mesma forma, iniciamos um ponteiro chamado ponteiro direito no último item da matriz.
  • Se o valor do elemento no ponteiro esquerdo for menos comparado ao ponto de articulação selecionado, movemos o ponteiro esquerdo para a esquerda (adicione +1 a ele) e continuamos repetindo-o até que o valor no ponteiro esquerdo seja maior do que o valor do ponto de pivô ou igual a ele.
  • Se o valor do elemento no ponteiro direito da lista for maior que o valor do elemento dinâmico, modificamos o ponteiro direito para a esquerda. Repita isso até que o valor no ponteiro do lado direito seja menor que (ou igual a) o valor do pivô.
  • Quando o valor do ponteiro esquerdo for menor ou igual ao valor do ponteiro direito, troque os valores.
  • Mova o ponteiro da direita para a esquerda por um, o ponteiro da esquerda para a direita em um.
  • Repita até que os ponteiros esquerdo e direito se encontrem.

Código:

function quickSortAlgo(origArray) (
if (origArray.length <= 1) (
return origArray;
) else (
var left = ();
var right = ();
var newArray = ();
var pivot = origArray.pop();
var length = origArray.length;
for (var i = 0; i < length; i++) (
if (origArray(i) <= pivot) (
left.push(origArray(i));
) else (
right.push(origArray(i));
)
)
return newArray.concat(quickSortAlgo(left), pivot, quickSortAlgo(right));
)
)
var myArray = (13, 50, 2, 45, -1, 74, 11 );
var arreySorted = quickSortAlgo(myArray);
console.log(arreySorted);

Resultado:

5. Algoritmo de Classificação por Inserção

Quando se trata de facilidade de implementação, a classificação por inserção é amplamente conhecida como um dos algoritmos mais simples. Em Classificação de inserção, os elementos da matriz são comparados entre si e, em seguida, organizados em uma ordem específica. Isso é muito semelhante a organizar cartas em um baralho. A ordenação por inserção de nome vem do processo de escolher um elemento e inseri-lo no lugar correto e, em seguida, repeti-lo para todos os elementos.

Aqui está como o algoritmo funciona:

  • O primeiro elemento da matriz é considerado já classificado.
  • Escolha o próximo elemento da matriz.
  • Compare o elemento selecionado com todos os elementos da matriz.
  • Mude todos os elementos da matriz que sejam maiores que o valor do elemento selecionado.
  • Inserir o elemento
  • Repita as etapas 2 a 5 até a matriz ser classificada.

Código:

function insertion_Sort_algo(arr)
(
for (var i = 1; i < arr.length; i++)
(
if (arr(i) < arr(0))
(
arr.unshift(arr.splice(i, 1)(0));
)
else if (arr(i) > arr(i-1))
(
continue;
)
else (
for (var j = 1; j < i; j++) (
if (arr(i) > arr(j-1) && arr(i) < arr(j))
(
arr.splice(j, 0, arr.splice(i, 1)(0));
)
)
)
)
return arr;
)
console.log(insertion_Sort_algo((44, 20, 26, 54, -9, 41, 16)));

Resultado:

6. Algoritmo de classificação de heap

A classificação de heap é uma maneira de classificar elementos usando a estrutura de dados "Heap". O método é bastante semelhante à técnica de classificação por seleção que discutimos anteriormente. Agora você pode estar se perguntando sobre os Heaps e como eles são definidos, antes de chegar ao algoritmo, vamos entender primeiro os heaps.

Em poucas palavras, um heap é uma árvore binária com algumas regras adicionais. Uma regra afirma que, no heap, a árvore deve ser uma árvore binária completa, o que significa simplesmente que é necessário preencher todos os nós no nível atual antes de adicionar outro. A próxima regra para a pilha é que deve haver um relacionamento filho e pai definido com os valores do elemento da pilha.

Em um min-heap, o valor de um pai deve ser menor que seus filhos. Em um heap máximo, como você pode imaginar, o valor de um pai deve ser maior que seu filho.

Agora que as definições estão fora do caminho, vamos dar uma olhada em como o heapsort funciona:

  • Primeiro, construímos um heap máximo que garante que o elemento de maior valor esteja no topo.
  • Alternamos o elemento superior com o último elemento do heap e removemos o elemento superior do heap e o armazenamos em uma matriz classificada.
  • Continuamos repetindo as etapas um e dois até restar apenas um elemento no heap.

Uma coisa a ter em mente é que o Heaps não é nativamente suportado em JavaScript, portanto, temos que recorrer à implementação do Heaps usando matrizes. A complexidade de espaço da classificação de heap é O (1), que é excelente e, embora seja um pouco mais complicada em comparação com a classificação de mesclagem ou inserção quando se trata de entendimento e implementação, acho que para obter benefícios de desempenho, é melhor usar grandes projetos.

Código:

var arrLength;
function heapRoot(input, i) (
var left = 2 * i + 1;
var right = 2 * i + 2;
var max = i;
if (left input(max)) (
max = left;
)
if (right input(max)) (
max = right;
)
if (max != i) (
swap(input, i, max);
heapRoot(input, max);
)
)
function swap(input, index_A, index_B) (
var temp = input(index_A);
input(index_A) = input(index_B);
input(index_B) = temp;
)
function heapSortAlgo(input) (
arrLength = input.length;
for (var i = Math.floor(arrLength / 2); i >= 0; i -= 1) (
heapRoot(input, i);
)
for (i = input.length - 1; i > 0; i--) (
swap(input, 0, i);
arrLength--;
heapRoot(input, 0);
)
)
var arr = (12, 10, 22, 55, -8, 64, 14);
heapSortAlgo(arr);
console.log(arr);

Resultado:

Conclusão

A classificação é uma parte importante da criação de aplicativos e sites com JavaScript. Agora que você está familiarizado com alguns dos algoritmos mais importantes para realizar o trabalho, você deve se sentir mais confiante no JS Development.

Um fato importante a ser lembrado sobre várias classificações é que você realmente não precisa se preocupar muito com o algoritmo a ser usado na maioria dos casos. Agora que o hardware do computador é tão poderoso, os modernos processadores de telefone e desktop não precisam se preocupar em classificar até centenas de elementos em alguns milissegundos. É apenas nos casos em que você fica com hardware lento ou em situações em que otimiza cada seção do código em que a alteração dos algoritmos de classificação pode ser benéfica.

Artigos recomendados

Este é um guia para ordenar algoritmos em JavaScript. Aqui discutimos os 6 principais algoritmos de classificação em javascript, juntamente com exemplos e implementação de código. Você também pode consultar os seguintes artigos para saber mais -

  1. Compiladores JavaScript
  2. Inverter em JavaScript
  3. Introdução ao JavaScript
  4. Quadrados em Java
  5. Algoritmos de classificação rápida em Java
  6. Matrizes na estrutura de dados
  7. Algoritmo C ++ | Exemplos de algoritmo C ++

Categoria:

Desenvolvimento de software