Top Algoritmi e Strutture dati che devi davvero conoscere

Se vuoi diventare un ingegnere del software, ma non sai da dove cominciare, ti risparmiamo la suspense: sono gli algoritmi e le strutture dati.

Una volta che avrai capito il succo di questi pilastri della programmazione, inizierai a vederli ovunque. E più algoritmi e strutture dati imparerete, più vi serviranno come carburante per la vostra carriera di ingegnere del software.

Per iniziare, facciamo prima un’immersione profonda in Search e Sort, due classi di algoritmi di cui non potete fare a meno. Poi facciamo una rapida panoramica del resto del panorama che include alberi, grafici, programmazione dinamica e molto altro.

In linea di massima, ci sono due categorie di algoritmi di ricerca che dovrete conoscere subito: lineare e binario. Anche la Depth First Search (DFS) e la Breadth First Search (BFS) sono super-importanti, ma le conserveremo per la sezione Graph Traversal che segue.

Ricerca lineare

Gli algoritmi lineari e binari sono chiamati così per descrivere quanto tempo (complessità temporale) una ricerca richiederà in base alla dimensione dell’input da ricercare.

Per esempio, con gli algoritmi di ricerca lineare, se si hanno 100 elementi da cercare, il caso peggiore richiederebbe di guardare ogni elemento dell’input prima di trovare il valore desiderato. Si chiama lineare perché il tempo necessario alla ricerca è esattamente correlato alla quantità di elementi nella ricerca (100 elementi/input =100 controlli/complessità)

In breve, lineare = semplice (non c’è nulla di intelligente nell’algoritmo). Per esempio: immaginate di cercare il vostro amico Lin tra una fila di persone in piedi senza un ordine particolare. Sapete già che aspetto ha Lin, quindi dovete semplicemente guardare ogni persona, una per una, in sequenza, finché non riconoscete o non riuscite a riconoscere Lin. Questo è quanto. Così facendo, stai seguendo l’algoritmo di ricerca lineare

Ricerca binaria

La ricerca binaria prende il suo nome perché la parola binaria significa “di o relativa a 2 cose” e l’algoritmo funziona dividendo l’input in due parti finché non trova l’elemento che viene cercato. Una metà contiene l’elemento di ricerca e l’altra metà no. Il processo continua fino a quando il punto in cui l’input viene diviso diventa l’elemento che viene cercato. La ricerca binaria è fondamentalmente solo un approccio altamente disciplinato al processo di eliminazione. È più veloce della ricerca lineare, ma funziona solo con sequenze ordinate.

Un esempio dovrebbe rendere questo più chiaro. Supponiamo che stiate cercando di trovare il vostro amico Bin (che è alto 1,5”) in una fila singola di persone che sono state ordinate per altezza da sinistra a destra, dal più basso al più alto. È una fila molto lunga, e non hai il tempo di percorrerla tutta uno per uno, confrontando l’altezza di tutti con quella di Bin. Cosa puoi fare?

Entra nella ricerca binaria. Si seleziona la persona al centro della fila e si misura la sua altezza. Sono 1 metro e 70. Così subito sai che questa persona, insieme a tutti quelli alla sua destra, non è Bin. Ora che hai dimezzato il tuo problema, rivolgi la tua attenzione al resto della fila e scegli di nuovo la persona di mezzo. Sono alti 1,4”. Quindi puoi escludere quella persona e chiunque alla sua sinistra, tagliando di nuovo il problema a metà. E così via. Dopo appena cinque o sei di queste divisioni, si arriva rapidamente a Bin in una frazione del tempo che ci è voluto per trovare Lin. Così facendo, avete seguito l’algoritmo di ricerca binaria.

Ordinamento

Ordinare, altrimenti noto come ordinamento, liste di elementi è uno dei compiti di programmazione più comuni che farete come sviluppatori. Qui vediamo due degli algoritmi di ordinamento più utili: MergeSort e QuickSort.

MergeSort

Immaginiamo che piuttosto che imbattersi nella linea ordinata di persone dell’esempio precedente, si debba creare una linea ordinata di persone da un gruppo non ordinato. Non avete molto tempo, quindi trovate una strategia per accelerare le cose.

Prima fate dividere il gruppo di persone, che sono tutte ammassate insieme, in due. Poi ognuno dei due gruppi si divide di nuovo in due, e così via, fino a quando si ha a che fare interamente con individui. Poi cominci ad accoppiare gli individui, e fai in modo che il più alto dei due in ogni coppia stia alla destra dell’altro. Ben presto tutti sono organizzati in queste coppie ordinate sinistra-destra.

Poi cominciate a fondere le coppie ordinate in gruppi ordinati di quattro; poi fondete i gruppi ordinati di quattro in gruppi ordinati di otto; e così via. Alla fine, si scopre che si ha una linea completa di persone ordinate in altezza, proprio come quella incontrata sopra. Senza saperlo, avete seguito l’algoritmo MergeSort per realizzare la vostra impresa.

QuickSort

QuickSort è un po’ troppo complesso per essere facilmente immaginato con le persone, quindi avviciniamoci un po’ di più al codice. Per iniziare, immaginiamo di avere una lista non ordinata, o array, di otto numeri che volete ordinare.

4 2 13 6 15 12 7 9

Potreste usare MergeSort, ma avete sentito che QuickSort è generalmente più veloce, quindi decidete di provarlo. Il tuo primo passo è quello di scegliere un numero nella lista chiamato pivot. Scegliere il giusto numero di pivot farà la differenza nella velocità di QuickSort, e ci sono formule già pronte da seguire per scegliere buoni pivot. Ma per ora, manteniamo le cose semplici e usiamo l’ultimo numero nell’array per il nostro numero pivot: 9.

4 2 13 6 15 12 7 9

Per rendere il prossimo passo più facile da seguire, creeremo un separatore all’inizio dell’array e lo rappresenteremo con il segno cancelletto.

# 4 2 13 6 15 12 7 9

Muovendoci da sinistra a destra attraverso la nostra matrice, il nostro obiettivo è quello di mettere ogni numero più piccolo del perno (9) a sinistra del separatore, e ogni numero maggiore (o uguale) al perno a destra del separatore. Iniziamo con il primo numero della nostra matrice: 4. Per spostarlo a sinistra del separatore, spostiamo semplicemente il separatore in alto di un elemento:

4 # 2 13 6 15 12 7 9

Facciamo lo stesso con il numero successivo: 2.

4 2 # 13 6 15 12 7 9

Ma poi arriviamo a 13, che è più grande del numero pivot 9 e già alla destra del separatore. Quindi lasciamo perdere. Poi arriviamo a 6, che deve andare a sinistra del separatore. Quindi prima lo scambiamo con il 13 per metterlo in posizione:

4 2 # 6 13 15 12 7 9

Poi spostiamo il separatore oltre:

4 2 6 # 13 15 12 7 9

Il prossimo è il 15, che è già alla destra del separatore, quindi lo lasciamo stare. Poi abbiamo il 12. Stessa cosa. Ma il 7, il nostro ultimo numero prima di raggiungere il perno, ha bisogno dello stesso tipo di aiuto per spostarsi del 6. Quindi scambiamo il 7 con il 13 per metterlo in posizione:

4 2 6 # 7 15 12 13 9

Poi, ancora una volta, facciamo passare il separatore:

4 2 6 7 # 15 12 13 9

Finalmente, arriviamo al nostro numero pivot: 9. Seguendo la stessa logica di cui sopra, scambiamo 15 con 9 per ottenere il numero pivot dove deve essere:

4 2 6 7 # 9 12 13 15

Siccome tutti i numeri a sinistra di 9 sono ora più piccoli di 9, e tutti i numeri a destra di 9 sono maggiori di 9, abbiamo finito il nostro primo ciclo di QuickSort. Successivamente, tratteremo ogni serie di quattro numeri su entrambi i lati del separatore come un nuovo array a cui applicare QuickSort. Vi risparmieremo i dettagli, ma il prossimo ciclo ci darà quattro coppie di numeri a cui applicare facilmente il nostro ciclo finale di QuickSort. Il risultato finale sarà la seguente lista ordinata che ha richiesto meno tempo per essere generata rispetto al più semplice MergeSort:

2 4 6 7 9 12 13 15

Scheda degli algoritmi di ordinamento

Questi sono gli algoritmi di ordinamento più comuni con alcune raccomandazioni su quando usarli. Internalizzateli! Sono usati ovunque!

Heap sort: Quando non avete bisogno di un ordinamento stabile e vi preoccupate più delle prestazioni nel caso peggiore che in quello medio. È garantito essere O(N log N), e usa O(1) spazio ausiliario, il che significa che non finirete inaspettatamente lo spazio di heap o di stack su input molto grandi.

Introsort: Questo è un ordinamento rapido che passa ad un ordinamento heap dopo una certa profondità di ricorsione per aggirare il caso peggiore O(N²) dell’ordinamento rapido. È quasi sempre meglio di un vecchio ordinamento rapido, poiché si ottiene il caso medio di un ordinamento rapido, con prestazioni garantite O(N log N). Probabilmente l’unica ragione per usare un heap sort invece di questo è in sistemi fortemente limitati dalla memoria, dove lo spazio di stack O(log N) è praticamente significativo.

Insertion sort: Quando N è garantito essere piccolo, anche come caso base di un ordinamento rapido o di un ordinamento misto. Mentre questo è O(N²), ha una costante molto piccola ed è un ordinamento stabile.

Bubble sort, selection sort: Quando state facendo qualcosa di veloce e sporco e per qualche ragione non potete semplicemente usare l’algoritmo di ordinamento della libreria standard. L’unico vantaggio che hanno rispetto all’ordinamento ad inserimento è che sono leggermente più facili da implementare.

Ordinamento rapido: Quando non avete bisogno di un ordinamento stabile e le prestazioni del caso medio contano più di quelle del caso peggiore. Un ordinamento rapido è O(N log N) in media, O(N²) nel caso peggiore. Una buona implementazione usa O(log N) di memoria ausiliaria sotto forma di spazio nello stack per la ricorsione.

Merge sort: Quando avete bisogno di un ordinamento stabile, O(N log N), questa è la vostra unica opzione. Gli unici aspetti negativi sono che usa O(N) spazio ausiliario e ha una costante leggermente più grande di un ordinamento rapido. Ci sono alcuni ordinamenti in-place merge, ma AFAIK sono tutti o non stabili o peggio di O(N log N). Anche gli ordinamenti in-place O(N log N) hanno una costante molto più grande del vecchio ordinamento rapido che sono più curiosità teoriche che algoritmi utili.