Algoritmi di ordinamento per principianti in JavaScript: Bubble, Selection & Insertion Sort

Avere i set di dati disposti tutti, volenti o nolenti, aggiungerà solo più tempo e risorse per gestire e cercare. Se i tuoi dati sono ordinati o meno influenzerà direttamente i metodi di ricerca che puoi utilizzare e può significare la differenza tra una ricerca che richiede un milione di operazioni o 10, come con la ricerca binaria.

Per semplicità, ci concentreremo solo sull’ordinamento di una serie di numeri dal minimo al massimo, ma questi algoritmi sono facilmente modificabili per altri obiettivi di ordinamento. Tieni presente che si tratta di concetti e modelli più generali e meno di un “how-to” per l’ordinamento dei dati poiché la tua particolare implementazione potrebbe differire molto, ma alla fine potrebbe assomigliare concettualmente a questi modelli.

Ecco la matrice pratica di 50 numeri casuali.

const unsortedArr = ;

Prerequisiti

Guarderò tutto attraverso la lente della notazione Big O, quindi capire come la complessità cresce nel tempo sarà molto utile.

Bubble Sort

Questo è il “Ciao mondo” dei metodi di ordinamento, niente di pazzo ma ottiene il lavoro fatto.

Per ogni elemento dell’array vogliamo verificare se l’elemento successivo è più grande, se è quindi scambiare i loro indici nell’array. Per evitare di ricomporre i numeri ordinati, inizieremo dal retro dell’array mentre un altro for loop ottiene il numero precedente. In questo modo tutti i valori più grandi si accumulano, o “bolle”, alla fine.

 Bubble Sort Animation

Grafica/Animazione grazie a VisuAlgo.net

La nostra versione funziona al contrario rispetto all’animazione, ma è abbastanza vicina.

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 funziona come l’opposto di Bubble sort, mentre bubble sort sta spingendo tutti i valori più grandi fino alla fine ora spingeremo i valori minimi all’inizio.

Ogni volta che esegue il loop sull’array seleziona il valore più piccolo, se trova un valore più basso che diventa il nuovo valore più basso. Quando il ciclo è finito, prenderà quel minimo e lo metterà sulla parte anteriore dell’array prima di ricominciare il ciclo. In questo modo il valore più basso di ogni iterazione viene impilato sul fronte fino a quando l’intero array non viene ordinato.

Selezione Ordina Animazione

Grafica/Animazione grazie a 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));

Insertion Sort

Il mio preferito e il più performante dei tre, insertion sort, è più simile a come ordineresti qualcosa a mano.

Guardiamo l’array come due parti, ordinate e non ordinate, con ogni volta che troviamo un nuovo valore torniamo indietro per trovare il suo posto nella metà ordinata. Con ogni aggiunta il nostro gruppo ordinato cresce fino a diventare l’intero array.

Inserimento Ordina Animazione

Grafica/Animazione grazie a 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));

Confronto

Un problema con l’utilizzo della notazione Big O per confrontare gli algoritmi è che si basa sullo scenario peggiore, che può essere lo stesso tra gli algoritmi dando la falsa illusione che siano uguali. Mentre i tipi di bolle, Selezione e inserimento sono tutti O(n^2), questo non ci dice molto sullo scenario medio o migliore o su come variano con la struttura dei dati.

L’ordinamento di inserimento vince ogni volta. Ha anche il vantaggio di non dover avere l’intero array prima di iniziare, il che consente di ordinare le cose in tempo reale man mano che i dati arrivano.

Tienilo a mente perché non dovresti decidere quale algoritmo è “migliore” prima di considerare come i tuoi dati sono già organizzati.

Conclusione

Questi tre sono lontani dalle migliori soluzioni per ordinare in modo efficiente grandi quantità di dati, ma sono alcuni dei più intuitivi per immergere le dita dei piedi in quello che può essere un oceano travolgente. 🌊