Timo Bingmann, dottorando del Karlsruhe Institute of Technology, ha recentemente pubblicato sul suo canale YouTube un video dal titolo 15 Sorting Algorithms in 6 Minutes. Nel video vengono visualizzati e sonorizzati 15 algoritmi di ordinamento.

A Martino Sykora, ingegnere informatico che si occupa di sviluppo di firmware embedded, abbiamo chiesto di vedere, poi spiegare e recensire, il video.
Segue, qui sotto, il suo saggio breve:

Il video mostra 15 algoritmi di ordinamento. Mi soffermerò solo su alcuni di questi, spiegandone il funzionamento. Preferisco concentrarmi su concetti generali: di cosa stiamo parlando, perché è importante ordinare, perché è importante farlo efficientemente.

COS’È UN ALGORITMO DI ORDINAMENTO
Un algoritmo di ordinamento è una sequenza di operazioni – codificata – per ordinare insiemi di dati. Nel video l’insieme di dati è formato da tante asticelle di diverse altezze. Prima dell’esecuzione dell’algoritmo le asticelle sono disposte alla rinfusa, in un ordine casuale. Dopo l’ordinamento la più bassa occupa la posizione all’estrema sinistra, la più alta all’estrema destra.

PERCHÈ È IMPORTANTE ORDINARE
Ordinare è importante perchè in un insieme ordinato è più facile cercare elementi. È più facile cercare in un insieme ordinato che in un insieme disordinato. Un esempio su tutti: l’elenco telefonico. Qui si aprirerebbe un capitolo legato agli algoritmi di ricerca efficiente. Se spendiamo tempo ed energia per ordinare i dati, vorremmo poi sfruttare i vantaggi che ne derivano.

Spendo due parole sugli algoritmi di ricerca. Il metodo di ricerca più intuitivo è la ricerca sequenziale. Ossia, passo in rassegna uno a uno gli elementi dell’insieme, fino a quando non trovo
quello che sto cercando (es: l’asticella lunga X). È anche l’unico metodo che possiamo applicare quando l’insieme è disordinato… Sarebbe però il più stupido da sfruttare in presenza di un ordinamento. È infatti estremamente inefficace e nel caso pessimo passeremmo in rassegna tutti gli elementi. Se gli elementi sono N, l’algoritmo farà al più N confronti!

Se l’insieme è stato precedentemente ordinato, al contrario, possiamo farci furbi e applicare una ricerca binaria (o dicotomica).
Confrontiamo l’elemento che vogliamo cercare con quello nel mezzo. Se l’elemento da cercare è maggiore si troverà nella seconda metà, se è minore nella prima metà. Supponiamo sia maggiore: ripetiamo l’operazione di confronto con il mediano, prendendo però in considerazione solo la metà superiore….e così via, ricorsivamente, fino a quando non troviamo il nostro elemento o non abbiamo più elementi con cui confrontarlo. Questa ricerca compie al massimo log_2(N) confronti (logaritmo in base due di N, dove N è il numero di elementi).

Puoi applicare questo metodo con un amico: chiedigli di pensare un numero tra 1 e 256. A questo punto dichiara che lo indovinerai al massimo in log_2(256) = 8 tentativi. Se applichi la ricerca dicotomica non potrai sbagliare. Un numero tra 1 e 1024 lo indovinerai al più in 10 tentativi! Visto quanto è efficiente lavorare su dati ordinati?

Esistono altri metodi di ricerca che sfruttano l’ordinamento. A esempio, quelli che assegnano un indice all’insieme di ordinamento e l’indice è organizzato come un albero binario (o N-ario). Se cerchi B-Tree su wikipedia trovi di tutto. Ma senza scendere nel tecnico, ti faccio un esempio calzante e tecnologicamente appartenente al secolo scorso: le agendine telefonichecartacee, con le loro brave linguette con le lettere. Ecco un esempio di indicizzazione. Se cerco il cognome Sykora aprirò subito la sezione Smuovendomi prima lungo l’indice e quindi all’interno della sezione di interesse.

COMPLESSITÀ COMPUTAZIONALE E SPAZIALE
Ancora un paio di nozioni prima di entrare nei dettagli di (alcuni) degli algoritmi nel video. Quando si parla di computazione ci sono due risorse – scarse – di cui i programmatori devono tenere conto.

1. Il tempo di esecuzione
2. Il consumo di memoria

Tradotto: un algoritmo dovrebbe essere il più veloce possibile e occupare meno memoria possibile. Trovare un tradeoff tra queste risorse è un must. Di solito essere veloci implica sprecare memoria, e vice versa. Si parla quindi, rispettivamente, di complessità computazionale e spaziale. Semplificando al massimo, se i dati di partenza sono lunghi N e l’algoritmo compie un numero di passi pari a f(N) – dove f(*) è una funzione –
per N che tende ad infinito si dice che ha complessità computazionale O(f(N)).
[Nota, la notazione O(*) – si pronuncia “o Grande” – è una notazione asintotica, la definizione che ho
dato sopra non è precisissima, ma il messaggio credo che sia passato]
In soldoni, un algoritmo che fa log(N) operazioni è più veloce di uno che ne fa N, che a sua volta è più veloce di uno che ne fa N^2 (N al quadrato) e così via.

Lo stesso concetto si può applicare alla complessità spaziale. Un algoritmo che ordina in place (ossia non ha bisogno di memoria aggiuntiva per ordinare un insieme di dati) ha complessità spaziale O(N), dove N, al solito, è la dimensione dell’insieme.

In informatica gli algoritmi vengono analizzati con tecniche formali per stabilirne la complessità computazionale e spaziale.

ANALISI DEGLI ALGORITMI NEL VIDEO
Come ti dicevo, mi soffermo solo su alcuni algoritmi, i più noti.
Alcuni tra quelli mostrati sono particolarmente esotici, altri sono super raffinati, altri sono a me sconosciuti…

SELECTION SORT
Il video si apre con il Selection Sort. È l’algoritmo di ordinamento più intuitivo, quello che qualunque operatore umano sfrutterebbe. Immagina di essere di fronte a un tavolo da biliardo. Le palle sono tutte sul tavolo, disposte a caso. Ti viene chiesto di ordinarle… che fai? Individui (SELECTION) quella con il numero più alto e la metti “in fondo” a una ipotetica fila. Poi ti concentri sulle restanti e ripeti il compito. Individui quella con il numero più alto e la metti accanto alla precedente… e così via. Il succo non cambia se invece che selezionare le palle con il numero più alto, tu avessi selezionato quelle con il numero più basso.

Questo è quello che fa l’algoritmo: seleziona l’asticella più bassa, la mette all’inizio, e poi itera il procedimento sugli elementi restanti.
È per questo motivo che vedi il triangolone prendere forma dalla punta (da sinistra verso destra, per intenderci). Questo è un algoritmo che ordina in place (non ha bisogno di strutture di appoggio) quindi la sua complessità spaziale è O(N).

È un algoritmo lento! La sua complessità temporale è O(N^2). Proviamo a calcolarla.

Innanzi tutto l’algoritmo deve cercare il minimo. L’insieme non è ordinato, quindi, deve passare in rassegna TUTTI gli N elementi per trovare il minimo, farà quindi N operazioni.

Poi fa uno scambio: scambia il minimo (l’asticella più bassa) con quella che sta in prima posizione. L’operazione di scambio ha costo costante, indipendentemente dal numero degli elementi, e quindi “scompare” dal nostro computo.

Quindi opererà le stesse operazioni sugli N-1 elementi restanti.

Quindi, alla fine, avrà fatto
N + (N-1) + (N-2) + (N-3) + ….. + 1

Questa sommatoria si dimostra per induzione matematica avere risultato N(N+1) / 2

Per N che tende ad infinito è asintotica a N^2, quindi O(N^2), CVD

BUBBLE SORT (minuto 4:00)
Altro algoritmo lento (quadratico, come il precedente) e “in place”.
È leggermente più efficiente del precedente, ma asintoticamente sono uguali.

Questo non fa altro che confrontare un elemento con il successivo.
Se il primo è maggiore del secondo, li scambia. E questo lo fa per tutti gli elementi. Questa operazione ha effetto di portare l’elemento massimo in fondo, una volta visitati tutti gli elementi.

Poi ripete l’operazione sugli elementi privati dell’elemento in fondo, e così via, su insiemi sempre più piccoli.

Il triangolo delle asticelle ordinate prende forma da destra verso sinistra, poichè gli elementi massimi vengono via via accumulati in fondo.

Perchè “Bubble”? Mah, forse perchè l’operazione di confronto di un elemento con il successivo e l’eventuale scambio ricordano lo scoppio di una “Bolla”, proprio non so

QUICK SORT [0:38]
Questo è uno degli algoritmi di ordinamento più efficienti, forse il più efficiente nel caso medio. È anche quello che è implementato nella stragrande maggiorande delle API (Application Programming Interface) informatiche. La sua complessità computazionale è abbastanza complicata da calcolare ed è O(Nlog_2(N)) [N per logaritmo in base 2 di N]. Quindi… poco più che lineare! Quindi… veloce!

La cosa curiosa è che nel caso pessimo è comunque quadratico O(N^2). Ma attenzione! Il worst case, in questo caso, è quello in cui l’insieme di partenza è già ordinato o quasi ordinato!
Un caso raro, quindi.

Come funziona? Sceglie un elemento chiamato PIVOT all’interno dell’insieme. Tanto si è dibattuto sui criteri di scelta del PIVOT… alcuni sono meglio di altri. Per ora ipotizziamo che il PIVOT venga scelto a caso, il succo non cambia.

Bene, scelto il PIVOT, lo scopo del gioco è metterlo “dove dovrebbe stare”. Questo si traduce nell’operazione di partizionamento. L’insieme di dati viene organizzato in modo da ottenere due partizioni: la prima conterrà tutti i numeri minori o uguali del pivot, la seconda tutti i numeri maggiori o uguali (al posto di “numero” puoi dire “asticella”, al posto di “minore” puoi dire “più bassa” etc etc). Attenzione: le due partizioni sono ancora disordinate al loro interno, l’unico che è al suo posto – e che fa da elemento di separazione – è proprio il pivot.

A questo punto di applica la RICORSIONE. Ovvero, la stessa tecnica la si applica per le due partizioni. Stiamo applicando di nuovo l’algoritmo, indipendentemente, sulle due partizioni. Quando non rimangono più partizioni, l’algoritmo termina.

Guardando il video è evidente la fase di partizionamento, che lavora via via su partizioni sempre più piccole. Il triangolo viene costruito “a blocchi” (le partizioni) di granularità sempre più fine.

Una cosa importante: ho introdotto il termine RICORSIONE.
La ricorsione è una tecnica informatica che prevede che una funzione informatica richiami se stessa. A che pro? Per svolgere lo stesso tipo di compito, in questo caso, su porzioni dell’insieme via via più piccole.

Usando una notazione matematica e banalizzando un po’, sarebbe come scrivere f(f(f(f(x)))).

Bene, per come sono organizzati i calcolatori, una “chiamata a funzione” informatica ha un costo, in termini di memoria. Viene consumata la memoria denominata STACK. Ogni “chiamata a funzione” necessita di un’area di memoria chiamata “frame di attivazione”. Perchè dico questo? Perchè gli algoritmi ricorsivi sono avidi di stack, quindi occhio! Pur essendo questo un algoritmo che ordina in place, la sua complessità spaziale non è lineare se implementato con la ricorsione (esiste anche una versione non ricorsiva)!.La ricorsione costa in termini di memoria!

Un’altra considerazione… In questo caso tiro in ballo il parallelismo. Su architetture parallele (multi processore), un processore potrebbe occuparsi dell’ordinamento di una partizione e un altro dell’ordinamento dell’altra partizione. E così via: a sua volta potremmo utilizzare altri 4 processori per ordinare le sottopartizioni, riducendo notevolmente il tempo di esecuzione.

MERGESORT [1:00]
È cugino del quick sort e altrettanto veloce. Anch’esso ha una soluzione ricorsiva. Divide l’insieme a metà, poi le due metà le divide a metà, e così via… Fino ad arrivare a tante “metà” di solo due elementi ciascuna. Le metà vengono ordinate (scambiando gli elementi se il primo è maggiore del secondo, altrimenti lasciandoli nel loro ordine) – FASE DI SORT. A questo punto le metà vengono fuse a due a due – FASE DI MERGE – avendo cura di mantenere l’ordinamento. Si ripete ricorsivamente il procedimento.

Nella pratica (esempio rubato a wikipedia), immaginiamo di avere un insieme di 8 elementi. [10 3 15 2 1 4 9 0]. Lo scomponiamo in 4 sottoinsiemi di due elemnti. [10 3] [15 2] [4 1] [9 0]. Ognuno dei sottoinsiemi viene ordinato, per un totale di 4 FASI DI SORT. [3 10] [2 15] [1 4] [0 9]. I primi due sottoinsiemi vengono fusi mantenendo l’ordine e lo stesso per gli ultimi due, per un totale di 2 FASI DI MERGE. Ora abbiamo due sottoinsiemi lunghi 4 e ordinati. [2 3 10 15] [0 1 4 9]. Con una ultima fase di merge li fondiamo mantenendo l’ordine, ottenendo come risultato di avere ordinato l’insieme di partenza. [0 1 2 3 4 9 10 15]. Ora dovrebbe esserti chiaro perchè vedi il triangolone finale prendere forma tramite tanti triangolini (sottoinsiemi ordinati) che vengono via via fusi (MERGE).

E I SUONI?

La parte “fashion” del video… 🙂
Mi sembra che siano stati assegnati dei suoni alle operazioni di selezione di elementi e di scambio. Mi sembra inoltre che tali suoni abbiano toni bassi (basse frequenze) in corrispondenza di asticelle piccole e alti in corrispondenza di asticelle alte.

Ti è piaciuto? Guarda anche Il videogame in stile anni Trenta.

 

SOURCEAlberto Motta, Wired
SHARE