algoritmos de classificação para iniciantes em JavaScript: Bubble, Selection & Insertion Sort

ter seus conjuntos de dados organizados, quer queira quer não, só adicionará mais tempo e recursos para gerenciar e pesquisar. Se seus dados são classificados ou não afetará diretamente quais métodos de pesquisa você pode usar e pode significar a diferença entre uma pesquisa que faz um milhão de operações ou faz 10, como com a pesquisa binária.

por uma questão de simplicidade, vamos nos concentrar apenas em classificar uma matriz de números do menor para o maior, mas esses algoritmos são facilmente modificáveis para outras metas de classificação. Lembre-se de que esses são conceitos e padrões mais gerais e menos de um “how-to” para classificar dados, pois sua implementação específica pode diferir muito, mas no final pode se assemelhar conceitualmente a esses padrões.

aqui está a matriz prática de 50 números aleatórios.

const unsortedArr = ;

pré-requisitos

vou olhar para tudo através das lentes da notação Big o, então entender como a complexidade cresce com o tempo será muito útil.

Bubble Sort

este é o “Hello World” de métodos de classificação, nada de louco, mas faz o trabalho.

Para cada item na matriz queremos verificar se o próximo item é maior, se for trocar seus índices na matriz. Para evitar recompar números classificados, começaremos na parte de trás da matriz, enquanto outro for loop obtém o número anterior. Desta forma, todos os maiores valores se acumulam, ou “bolhas”, no final.

animação de classificação de bolhas

gráfico/animação graças a VisuAlgo.net

nossa versão funciona ao contrário da animação, mas está perto o suficiente.

const bubble = arr => { const swap = (list, a, b) => , list] = , list]; for (let i = arr.length; i > 0; i--) { for (let j = 0; j < i - 1; j++) { if (arr > arr) swap(arr, j, j + 1); }; }; return arr;};console.log(bubble(unsortedArr));

Selection Sort

Selection sort funciona como o oposto de Bubble sort, enquanto bubble sort está empurrando todos os maiores valores para o fim agora vamos empurrar os valores mínimos para o início.

toda vez que ele percorre a matriz, ele seleciona o menor valor, se encontrar um valor menor que se torne o novo valor mais baixo. Quando o loop for concluído, ele levará esse mínimo e o colocará na frente da matriz antes de iniciar o loop novamente. Dessa forma, o valor mais baixo de cada iteração é empilhado na frente até que toda a matriz seja classificada.

animação de classificação de seleção

gráfico/animação graças ao VisuAlgo.net

const selection = arr => { const swap = (list, a, b) => , list] = , list]; arr.forEach((item, i) => { let min = i; for (let j = i + 1; j < arr.length; j++) { if (arr < arr) min = j; }; swap(arr, i, min); }); return arr;};console.log(selection(unsortedArr));

tipo de inserção

meu favorito pessoal e o mais performante dos três, tipo de inserção, é mais semelhante a como você classificaria algo manualmente.

olhamos para a matriz como duas partes, a classificada e a não classificada, com cada vez que encontramos um novo valor, fazemos um loop de volta para encontrar seu lugar na metade classificada. A cada adição, nosso grupo classificado cresce até que seja toda a matriz.

animação de classificação de inserção

gráfico/animação graças ao VisuAlgo.net

const insertion = arr => { arr.forEach((item, i) => { let num = arr; let j; for (j = i - 1; j >= 0 && arr > num; j--) { arr = arr; }; arr = num; }); return arr;};console.log(insertion(unsortedArr));

comparação

um problema com o uso de notação Big o para comparar algoritmos é que ele é baseado no cenário de pior caso, que pode ser o mesmo entre algoritmos dando a falsa ilusão de que eles são iguais. Embora os tipos de bolha, seleção e inserção sejam todos O(n^2), isso não nos diz muito sobre o cenário médio ou melhor caso ou como eles variam com a estrutura de dados.

a classificação de inserção vence todas as vezes. Ele também tem o benefício de não precisar ter toda a matriz antes de iniciar, o que permite classificar as coisas em tempo real à medida que os dados entram.

tenha isso em mente porque você não deve decidir qual algoritmo é “melhor” antes de considerar como seus dados já estão organizados.

conclusão

esses três estão longe de ser as melhores soluções para classificar com eficiência grandes quantidades de dados, mas são alguns dos mais intuitivos para mergulhar os dedos do pé no que pode ser um oceano esmagador. 🌊