Cos'è un Algoritmo di Grafo?

Gli algoritmi di grafo sono un insieme di istruzioni per attraversare (visitare i nodi di) un grafo.

Alcuni algoritmi sono usati per trovare uno specifico nodo o il percorso tra due dati nodi.

Perché gli Algoritmi di Grafo Sono Importanti

I grafi sono strutture dati molto utili che possono essere usate per modellare diversi problemi. Questi algoritmi hanno applicazione diretta nei siti di Social Network, nella modellazione di Macchine a Stati e molto altro.

Alcuni Comuni Algoritmi di Grafo

Alcuni dei più comuni sono:

• Ricerca in Ampiezza - Breadth First Search (BFS)
• Ricerca in Profondità - Depth First Search (DFS)
• Algoritmo di Dijkstra
• Algoritmo di Floyd-Warshall

Algoritmo di Bellman Ford

L'algoritmo di Bellman Ford è l'algoritmo per trovare il percorso più breve per grafi che possono avere pesi negativi. Questo algoritmo è anche valido per rilevare cicli di pesi negativi visto che l'algoritmo converge verso una soluzione ottimale in O(V*E) passaggi. Se quanto risultato non è ottimale, allora il grafo contiene un ciclo di peso negativo.

Ecco un'implementazione in  Python:

infinity = 1e10

def bellman_ford(graph, start, end):
    num_vertices = graph.get_num_vertices()
    edges = graph.get_edges()

    distance = [infinity for vertex in range(num_vertices)]
    previous = [None for vertex in range(num_vertices)]

    distance[start] = 0
    for i range(end+1):
        for (u, v) in edges:
            if distance[v] > distance[u] + graph.get_weight(u, v):
                distance[v] = distance[u] + graph.get_weight(u, v)
                previous[v] = u

    for (u,v) in edges:
        if distance[v] > distance[u] + graph.get_weight(u, v):
            raise NegativeWeightCycleError()
    return distance, previous
# 'distance' è la distanza dall'inizio verso quel nodo con il
# percorso più breve, utile per stampare la distanza più breve.
# 'previous' è un array che contiene il nodo che viene prima di 
# quello corrente, utile per stampare il percorso.

Ricerca in Profondità - Deep Search First (DFS)

È uno dei più semplici algoritmi di grafo. Attraversa il grafo prima verificando il nodo corrente, poi spostandosi verso uno dei suoi successori e ripetendo il processo. Se il nodo corrente non ha successori da verificare, torna indietro al suo predecessore e il processo continua (spostandosi verso un altro successore). Se viene trovata la soluzione la ricerca si arresta.

Implementazione (C++14)

#include <iostream> 
#include <vector> 
#include <queue>  
#include <algorithm>
using namespace std; 
 
class Graph{ 
   int v;    // numero di vertici 
 
   // puntatore a un vettore che contiene una lista di adiacenze
   vector < int > *adj;
public: 
   Graph(int v);  // Costruttore 
 
   // funzione per aggiugere una connessione tra due nodi (edge)
   void add_edge(int v, int w);  
 
   // stampa l'attraversamento dfs da una data sorgente `s` 
   void dfs();
   void dfs_util(int s, vector < bool> &visited);   
}; 
 
Graph::Graph(int v){ 
   this -> v = v; 
   adj = new vector < int >[v]; 
} 
 
void Graph::add_edge(int u, int v){ 
   adj[u].push_back(v); // aggiunge v alla lista u
   adj[v].push_back(v);  // aggiunge u alla lista v (elimina questa istruzione se il grafo è diretto!)
} 
void Graph::dfs(){
   // vettore dei visitati - per tenere traccia dei visitati durante la ricerca DFS
   vector < bool > visited(v, false);  // marca tutti i nodi/vertici come non visitati
   for(int i = 0; i < v; i++)
       if(!visited[i])
           dfs_util(i, visited);
} 
// nota l'utilizzo di una chiamata per riferimento qui!
void Graph::dfs_util(int s, vector < bool > &visited){ 
   // marca il nodo/vertice corrente come visitato
   visited[s] = true;
    // stampa allo standard output (schermo)
   cout << s << " ";
   
   // attraversa la suo lista di adiacenze e chiama ricorsivamente dfs_util per tutti i suoi vicini!
   // (solo se il vicino non è ancora stato visitato!)
   for(vector < int > :: iterator itr = adj[s].begin(); itr != adj[s].end(); itr++)
       if(!visited[*itr])
           dfs_util(*itr, visited); 
} 
 
int main() 
{ 
   // crea un grafo usando la classe Graph definita qui sopra
   Graph g(4); 
   g.add_edge(0, 1); 
   g.add_edge(0, 2); 
   g.add_edge(1, 2); 
   g.add_edge(2, 0); 
   g.add_edge(2, 3); 
   g.add_edge(3, 3); 
 
   cout << "Il seguente è l'attraversamento Deep First del grafo fornito"
        << "(a partire dal vertice 0): "; 
   g.dfs(); 
   // il risultato sarebbe: 0 1 2 3
   return 0; 
} 

Valutazione

Complessità di spazio: O(n)

Complessità temporale per il caso peggiore O(n). Depth First Search è completo su una serie di nodi finita. Funziona meglio su alberi shallow (vale a dire alberi che hanno una piccola altezza o profondità, cioè un limitato numero di livelli o strati - n.d.t.).

Implementazione di DFS in C++

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

struct Graph{
	int v;
	bool **adj;
	public:
		Graph(int vcount);
		void addEdge(int u,int v);
		void deleteEdge(int u,int v);
		vector<int> DFS(int s);
		void DFSUtil(int s,vector<int> &dfs,vector<bool> &visited);
};
Graph::Graph(int vcount){
	this->v = vcount;
	this->adj=new bool*[vcount];
	for(int i=0;i<vcount;i++)
		this->adj[i]=new bool[vcount];
	for(int i=0;i<vcount;i++)
		for(int j=0;j<vcount;j++)
			adj[i][j]=false;
}

void Graph::addEdge(int u,int w){
	this->adj[u][w]=true;
	this->adj[w][u]=true;
}

void Graph::deleteEdge(int u,int w){
	this->adj[u][w]=false;
	this->adj[w][u]=false;
}

void Graph::DFSUtil(int s, vector<int> &dfs, vector<bool> &visited){
	visited[s]=true;
	dfs.push_back(s);
	for(int i=0;i<this->v;i++){
		if(this->adj[s][i]==true && visited[i]==false)
			DFSUtil(i,dfs,visited);
	}
}

vector<int> Graph::DFS(int s){
	vector<bool> visited(this->v);
	vector<int> dfs;
	DFSUtil(s,dfs,visited);
	return dfs;
}

Algoritmo di Floyd Warshall

È un ottimo algoritmo per trovare la distanza più breve tra tutti i vertici in un grafo. È un algoritmo molto conciso e una complessità temporale di O(V^3) (dove V è il numero dei vertici). Può essere usato con pesi negativi, anche se i cicli di pesi negativi non devono essere presenti nei grafi.

Valutazione

Complessità di spazio: O(V^2)

Complessità temporale per il caso peggiore: O(V^3)

Implementazione Python

# Un grande valore come infinito
inf = 1e10 

def floyd_warshall(weights):
    V = len(weights)
    distance_matrix = weights
    for k in range(V):
        next_distance_matrix = [list(row) for row in distance_matrix] # fa una copia della matrice di distanze
        for i in range(V):
            for j in range(V):
                # Sceglie se il vertice k può andare bene come percorso con una distanza minore
                next_distance_matrix[i][j] = min(distance_matrix[i][j], distance_matrix[i][k] + distance_matrix[k][j])
        distance_matrix = next_distance_matrix # update
    return distance_matrix

# Un grafo rappresentato come matrice delle adiacenze 
graph = [
    [0, inf, inf, -3],
    [inf, 0, inf, 8],
    [inf, 4, 0, -2],
    [5, inf, 3, 0]
]

print(floyd_warshall(graph))

Ricerca in Ampiezza - Breadth First Search (BFS)

È uno degli algoritmi di grafo più semplici. Attraversa il grafo prima verificando il nodo corrente, quindi espandendosi aggiungendo i suoi successori al livello successivo. Questo processo viene ripetuto per tutti i nodi nel livello corrente prima di spostarsi a quello successivo. Se la soluzione viene trovata, la ricerca si arresta.

Visualizzazione

Valutazione

Complessità di spazio: O(n)

Complessità per il caso peggiore: O(n)

La Ricerca in Ampiezza è completa su un insieme finito di nodi e ottimale se il costo dello spostamento da un nodo all'altro è costante.

Codice C++ per l'implementazione di BFS

// Programma per stampre l'attraversamento BFS da un dato
// vertice sorgente. BFS(int s) attraversa i vertici
// raggiungibili da s
#include<iostream> 
#include <list> 
  
using namespace std; 
  
// Questa classe rappresenta un grafo diretto usando una
// rappresentazione con lista di adiacenze
class Graph 
{ 
    int V;    // No. of vertices 
  
    // Puntatore a un array che contiene una lista di adiacenze
    list<int> *adj;    
public: 
    Graph(int V);  // Costruttore
  
    // funczione per aggiungere una connessione tra due nodi (edge) al grafo
    void addEdge(int v, int w);  
  
    // stampa l'attraversamento BFS da una data sorgente s
    void BFS(int s);   
}; 
  
Graph::Graph(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; 
} 
  
void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w); // Add w to v’s list. 
} 
  
void Graph::BFS(int s) 
{ 
    // marca tutti i vertici come non visitati
    bool *visited = new bool[V]; 
    for(int i = 0; i < V; i++) 
        visited[i] = false; 
  
    // Crea una coda per BFS 
    list<int> queue; 
  
    // Marca il nodo corrente come visitato e lo accoda
    visited[s] = true; 
    queue.push_back(s); 
  
    // 'i' verrà usato per ottenere tutti i vertici 
    // adiacenti di un vertice
    list<int>::iterator i; 
  
    while(!queue.empty()) 
    { 
        // Fa uscire un vertice dalla code e lo stampa
        s = queue.front(); 
        cout << s << " "; 
        queue.pop_front(); 
  
        // Ottiene tutti i vertici adiacenti di quello 
        // tolto dalla coda s. Se una adiacente non è stato
        // visitato, viene marcato come visitato e accodato
        for (i = adj[s].begin(); i != adj[s].end(); ++i) 
        { 
            if (!visited[*i]) 
            { 
                visited[*i] = true; 
                queue.push_back(*i); 
            } 
        } 
    } 
} 
  
// Programma per testare i metodi della classe Graph
int main() 
{ 
    // Crea un grafo dato il diagramma seguente
    Graph g(4); 
    g.addEdge(0, 1); 
    g.addEdge(0, 2); 
    g.addEdge(1, 2); 
    g.addEdge(2, 0); 
    g.addEdge(2, 3); 
    g.addEdge(3, 3); 
  
    cout << "Il seguente è un attraversamento Breadth First Traversal "
         << "(a partire dal vertice 2) \n"; 
    g.BFS(2); 
  
    return 0; 
}

Algoritmo di Dijkstra

È un algoritmo presentato da E.W. Dijkstra. Cerca la sorgente del percorso più breve in un grafo con connessioni (edge) non negative (perché?).

Creiamo 2 array: visited e distance, che registrano rispettivamente se un vertice è visitato e qual è la distanza minima dal vertice sorgente. Inizialmente l'array visited viene assegnato con valori false e distance come infinito.

Partiamo dal vertice sorgente, che sarà u, e i suoi vertici adiacenti v. Ora per ogni v che è adiacente a u, la distanza è aggiornata se non è stato visitato prima e la distanza da u è minore della distanza corrente. Poi selezioniamo il vertice successivo con la distanza minore e che non sia stato ancora visitato.

Una coda di priorità è spesso usata per soddisfare quest'ultimo requisito nel minor tempo. Qui sotto un'implementazione della stessa idea usando PriorityQueue in Java.

import java.util.*;
public class Dijkstra {
    class Graph {
	LinkedList<Pair<Integer>> adj[];
	int n; // Numero di vertici.
	Graph(int n) {
	    this.n = n;
	    adj = new LinkedList[n];
	    for(int i = 0;i<n;i++) adj[i] = new LinkedList<>();
	}
	// aggiunge una connessione tra i vertici a e b con il costo come peso	public void addEdgeDirected(int a, int b, int cost) {
	    adj[a].add(new Pair(b, cost));
	}
	public void addEdgeUndirected(int a, int b, int cost) {
	    addEdgeDirected(a, b, cost);
	    addEdgeDirected(b, a, cost);
	}
    }
    class Pair<E> {
	E first;
	E second;
	Pair(E f, E s) {
	    first = f;
	    second = s;
	}
    }

    // Comparator per ordinare gli oggetti Pairs nella Priority Queue
    class PairComparator implements Comparator<Pair<Integer>> {
	public int compare(Pair<Integer> a, Pair<Integer> b) {
	    return a.second - b.second;
	}
    }

    // Calola il percorso più corto dalla sorgente per ogni vertice e ritorna la distanza
    public int[] dijkstra(Graph g, int src) {
	int distance[] = new int[g.n]; // la distanza più breve di ciascun vertice da src
	boolean visited[] = new boolean[g.n]; // il vertice è visitato o no
	Arrays.fill(distance, Integer.MAX_VALUE);
	Arrays.fill(visited, false);
	PriorityQueue<Pair<Integer>> pq = new PriorityQueue<>(100, new PairComparator());
        pq.add(new Pair<Integer>(src, 0));
	distance[src] = 0;
	while(!pq.isEmpty()) {
	    Pair<Integer> x = pq.remove(); // Estrae il vertice con la distanza più breve da src
	    int u = x.first;
	    visited[u] = true;
	    Iterator<Pair<Integer>> iter = g.adj[u].listIterator();
	    // Itera sui vicini di u e aggiorna le loro distanze
	    while(iter.hasNext()) {
		Pair<Integer> y = iter.next();
		int v = y.first;
		int weight = y.second;
		// Verifica se il vertice v non è visitato
		// Se il nuovo percorso attraverso u offre un costo minore allora aggiorna l'array distance e aggiungi a pq
		if(!visited[v] && distance[u]+weight<distance[v]) {
		    distance[v] = distance[u]+weight;
		    pq.add(new Pair(v, distance[v]));
		}
	    }
	}
	return distance;
    }

    public static void main(String args[]) {
	Dijkstra d = new Dijkstra();
	Dijkstra.Graph g = d.new Graph(4);
	g.addEdgeUndirected(0, 1, 2);
	g.addEdgeUndirected(1, 2, 1);
	g.addEdgeUndirected(0, 3, 6);
	g.addEdgeUndirected(2, 3, 1);
	g.addEdgeUndirected(1, 3, 3);

	int dist[] = d.dijkstra(g, 0);
	System.out.println(Arrays.toString(dist));
    }
}

Algoritmo di Ford Fulkerson

Questo algoritmo risolve il problema del massimo flusso del grafo. Trova la migliore soluzione di flusso tramite le connessioni (edge) dei grafi in modo da ottenere il massimo flusso in uscita dall'altra parte. La sorgente ha una specifica velocità di input e ciascuna connessione ha un peso associato a essa che è la quantità massima che può passare attraverso quella connessione.

L'algoritmo di Ford Fulkerson è anche chiamato algoritmo di Edmund-Karp visto che le specifiche complete sono state fornite da Jack Edmonds e Richard Karp.

Funziona creando percorsi di aumento, ovvero percorsi dalla sorgente all'uscita che hanno un flusso non zero. Facciamo passare il flusso attraverso i percorsi e aggiorniamo i limiti. Ciò può portare a situazioni in cui non abbiamo più mosse disponibili. Ecco dove la capacità di "annullamento" di questo algoritmo gioca un ruolo importante. In caso di blocco, diminuiamo il flusso e apriamo la connessione per far passare la nostra sostanza corrente.

Passaggi

1. Imposta il flusso a zero per tutte le connessioni.
2. Fintanto che c'è un percorso dalla sorgente allo scarico:
3. Cerca il peso minimo sul percorso, che associ a  limit .
4. Trova tutte le connessioni (u, v) sul percorso e:
   1. Aggiungi  limit  al flusso da u a v. (Per la mossa corrente)
   2. Sottrai  limit  dal flusso da v a u (Per un annullamento della mossa in futuro)

Valutazione

Complessità temporale: O(V*E^2)

Implementazione Python

# Un numero grande per infinito
inf = 1e10

def maximum_flow(graph, source, sink):
  max_flow = 0
  parent = bfs(graph, source, sink)
  while path:
    limit = inf
    v = sink
    while v != source:
        u = parent[s]
        path_flow = min(limit, graph[u][v])
        v = parent[v]
    max_flow += path_flow

    v = sink
    while v != source:
        u = parent[v]
        graph[u][v] -= path_flow
        graph[v][u] += path_flow
        v = parent[v]

    path = bfs(graph, source, sink)
  return max_flow

Sai davvero cos'è la notazione O grande? Se lo sai, allora questo sarà un ripasso in previsione di un colloquio di lavoro. In caso contrario, non preoccuparti – unisciti a me in questo viaggio nell'informatica.

Se hai frequentato dei corsi riguardanti gli algoritmi, hai probabilmente sentito il termine notazione O grande. Se non ne hai mai sentito parlare, lo faremo a breve, per poi raggiugere un comprensione più approfondita di cosa è realmente.

La notazione O grande è uno degli strumenti fondamentali a disposizione degli informatici, così come per gli ingegneri del software, per analizzare il costo di un algoritmo.

Questo articolo è scritto con il presupposto che tu abbia già avuto a che fare con del codice. Inoltre, alcuni materiali approfonditi richiedono conoscenze di base di matematica a livello di scuola superiore, quindi possono essere poco adatti a principianti assoluti. Ma sei ti senti pronto, iniziamo!

In questo articolo, avremo una discussione approfondita riguardo alla notazione O grande. Inizieremo con un esempio di algoritmo per iniziare a capirne qualcosa. Poi passeremo alla matematica per ottenere una comprensione più formale. In seguito parleremo di alcune variazioni comuni di notazione O grande. Alle fine discuteremo di alcune limitazioni di O grande in situazioni pratiche. Di seguito è possibile vedere un sommario.

Sommario

1. Cos'è la notazione O grande e perché è importante
2. Definizione formale di notazione O grande
3. O grande, o piccola, Omega e Theta
4. Confronto di complessità tra valori tipici di O grande
5. Complessità temporale e spaziale
6. Complessità attesa, caso migliore, medio e peggiore
7. Perché O grande non conta
8. In conclusione…

Iniziamo!

1. Cos'è la notazione O grande e perché è importante

“La notazione O grande è una notazione matematica che descrive il comportamento asintotico di una funzione quando l'argomento tende a un particolare valore o a infinito. È un membro della famiglia di notazioni inventate da Paul Bachmann, Edmund Landau e altri, collettivamente chiamate notazione Bachmann–Landau o notazione asintotica.”

— Definizione di notazione O grande da Wikipedia

In parole povere, la notazione O grande descrive la complessità di un codice usando termini algebrici.

Per capire cos'è la notazione O grande, possiamo dare un'occhiata a un tipico esempio, O(n²). La lettera “n” rappresenta la dimensione dell'input e la funzione “g(n) = n²” all'interno di “O()” ci dà un'idea di quanto sia complesso l'algoritmo rispetto alla dimensione dell'input.

Un tipico algoritmo con complessità pari a O(n²) è l'algoritmo selection sort, un algoritmo di ordinamento che itera su una lista per assicurare che ogni elemento all'indice i sia l'i-esimo elemento più piccolo/grande della lista. Il CODEPEN qui sotto fornisce un esempio visuale.

L'algoritmo può essere descritto con il seguente codice. Per assicurare che l'elemento i-esimo sia l'i-esimo elemento più piccolo nella lista (indicato come SmallestElement nello snippet di codice seguente), questo algoritmo itera prima sulla lista con un loop for. Poi, per ogni elemento utilizza un altro loop per trovare l'elemento più piccolo nella parte restante della lista.

SelectionSort(List) {
  for(i from 0 to List.Length) {
    SmallestElement = List[i]
    for(j from i to List.Length) {
      if(SmallestElement > List[j]) {
        SmallestElement = List[j]
      }
    }
    Swap(List[i], SmallestElement)
  }
}

In questa situazione, consideriamo la variabile List come input, dunque la dimensione dell'input n è il numero di elementi all'interno di List. Assumendo che l'istruzione if e l'assegnazione del valore legata all'istruzione if necessiti di un tempo costante, possiamo trovare la notazione O grande per la funzione SelectionSort analizzando quante volte vengono eseguite le istruzioni.

Le istruzioni nel loop interno vengono eseguite n volte. Dopo che i viene incrementata, il loop interno viene eseguito n-1 volte, e così via finché non viene eseguito una volta, prima che entrambi i loop for raggiungano le condizioni di terminazione.

Alla fine ci ritroviamo con la somma di una serie geometrica, e con un po' di matematica da scuole superiori possiamo trovare che il loop interno viene ripetuto 1 + 2... + n volte, ovvero n(n-1)/2 volte. Moltiplicando otteniamo n²/2-n/2.

Quando calcoliamo la notazione O grande ci interessiamo solo dei termini dominanti, senza curarci dei coefficienti. Quindi, prendiamo n² come O grande finale e scriviamo O(n²).

Ora potresti chiederti perché si riduce tutto al “termine dominante” e perché non ci interessiamo dei coefficienti. Non preoccuparti, affronteremo questi aspetti uno alla volta. Potrebbe essere un po' difficile da capire all'inizio ma diventerà tutto più sensato man mano che leggerai la prossima sezione.

2. Definizione formale di notazione O grande

C'era una volta un re indiano che voleva ricompensare un uomo saggio per la sua bravura. Il saggio chiese nient'altro che il grano che potesse riempire una scacchiera.

Ma queste erano le sue regole: nella prima casella voleva 1 chicco di grano, poi 2 nella seconda casella, 4 nella successiva e così via, in modo che ogni casella della scacchiera fosse riempita con una quantità di grano pari al doppio della precedente. Il re ingenuo acconsentì senza esitazione, pensando che sarebbe stata una domanda banale da soddisfare, finché non provò a farlo...

Quindi, quanti chicchi di grano doveva il re al saggio? Sappiamo che una scacchiera contiene 8 caselle per 8 caselle, per un totale di 64, dunque la casella finale dovrebbe contenere un totale di 2⁶³ chicchi di grano. Se fai il calcolo, otterrai 1.8446744*10¹⁹, ovvero circa 18 seguito da 18 zeri. Assumendo che ogni chicco di grano pesi 0.01 grammi, il totale è 184,467,440,737 tonnellate di grano. E 184 miliardi di tonnellate sono parecchie, non è vero?

Da un certo punto, i numeri crescono piuttosto velocemente per via dell'andamento esponenziale. La stessa logica vale per gli algoritmi informatici. Se l'impegno richiesto per svolgere un'azione cresce esponenzialmente con la dimensione dell'input, può finire per diventare estremamente grande.  

Come vedremo a breve, la crescita di 2ⁿ è molto più rapida rispetto a n². Con n = 64, il quadrato di 64 è 4096. Se aggiungi questo numero a 2⁶⁴, verrà perso al di fuori delle cifre significative.

Ecco perché, quando ci interessa la velocità di crescita, ci concentriamo sui termini dominanti. E dato che vogliamo analizzare la crescita rispetto alle dimensioni dell'input, i coefficienti che moltiplicano solo il numero, piuttosto che crescere con le dimensioni dell'input, non contengono informazioni utili.

Qui sotto puoi vedere la definizione formale di O grande:

f(N) = O(g(N)), se esistono costanti positive c, N₀ tali che
f(N) ≤ c · g(N) per ogni N ≥ N₀

La definizione formale è utile quando devi svolgere una prova di matematica. Ad esempio, la complessità temporale di selection sort può essere definita dalla funzione f(n) = n²/2-n/2, come abbiamo discusso nella sezione precedente.

Se la nostra funzione g(n) è n², possiamo trovare una costante c = 1 e una N₀ = 0, e finché N > N₀, N² sarà sempre più grande di N²/2-N/2. Possiamo provarlo facilmente sottraendo N²/2 da entrambe le funzioni, poi possiamo vedere facilmente che N²/2 > -N/2 è vero quando N > 0. Dunque, possiamo giungere alla conclusione che f(n) = O(n²).

Potresti aver notato un piccolo trucchetto qui. Ovvero, se g(n) cresce velocemente, molto più veloce di qualsiasi cosa, O(g(n)) sarà sempre abbastanza grande. Ad esempio, per una funzione polinomiale, puoi avere sempre ragione dicendo che è O(2ⁿ) perché 2ⁿ alla fine supererà qualsiasi polinomio.

Matematicamente è corretto, ma in generale, quando parli di O grande, occorre conoscere l'estremo della funzione. Ne capirai di più leggendo la prossima sezione.

Ma prima di andare avanti, testiamo la tua comprensione con la seguente domanda. La risposta può essere trovata nelle sezioni successive.

Domanda: un'immagine è rappresentata da un array 2D di pixel. Se utilizzi un loop for annidato per iterare su ogni pixel (ovvero, hai un loop for che itera su tutte le colonne e un altro loop for che itera su tutte le righe), qual è la complessità temporale dell'algoritmo quando l'immagine è considerata come input?

3. O grande, o piccola, Omega e Theta

O grande: “f(n) è O(g(n))” se e solo se per delle costanti c e N₀, f(N) ≤ cg(N) per ogni N > N₀

Omega: “f(n) è Ω(g(n))” se e solo se per delle costanti c e N₀, f(N) ≥ cg(N) per ogni N > N₀

Theta: “f(n) è Θ(g(n))” se e solo se f(n) è O(g(n)) e f(n) è Ω(g(n))

o piccola: “f(n) è o(g(n))” se e solo se f(n) è O(g(n)) e f(n) non è Θ(g(n))

— Definizione formale di O grande, omega, theta e o piccola

In parole povere:

• O grande (O()) descrive il limite superiore della complessità.
• Omega (Ω()) descrive il limite inferiore della complessità.
• Theta (Θ()) descrive il limite asintotico stretto della complessità.
• o piccola (o()) descrive il limite superiore escludendo il limite stretto.

Ad esempio, la funzione g(n) = n² + 3n è O(n³), o(n⁴), Θ(n²) e Ω(n). Ma sarebbe ancora corretto se dicessi che è Ω(n²) oppure O(n²).

In generale, quando parliamo di O grande, ciò intendiamo in realtà è theta. È piuttosto insensato quando il limite superiore è molto più grande dell'ambito dell'analisi. Sarebbe un po' come risolvere diseguaglianze mettendo ∞ dal lato più grande, cosa che ti farebbe avere ragione praticamente quasi sempre.

Ma come determiniamo quali funzioni sono più complesse di altre? Lo scoprirai nella prossima sezione e imparandolo nel dettaglio.

4. Confronto di complessità tra valori tipici di O grande

Se tentiamo di calcolare la O grande per una particolare funzione g(n), ci interessa solo il termine dominante della funzione. Il termine dominante è il termine che cresce più velocemente.

Ad esempio, n² cresce più velocemente di n, quindi se abbiamo qualcosa come g(n) = n² + 5n + 6, sarà O(n²). Se hai seguito qualche corso di analisi, tutto ciò è molto simile alla scorciatoia per trovare il limite per polinomi frazionari, dove alla fine ti interessa solo il termine dominante per numeratori e denominatori.

Ma quale funzione cresce più velocemente delle altre? Per determinarlo esistono alcune regole.

1. O(1) ha la complessità minore

Spesso chiamato "tempo costante", se crei un algoritmo che risolve un problema in O(1), sei probabilmente al massimo delle tue possibilità. In alcuni casi, la complessità può andare oltre O(1), e puoi analizzarli trovando la sua controparte O(1/g(n)). Ad esempio, O(1/n) è più complessa di O(1/n²).

2. O(log(n)) è più complessa di O(1), ma meno complessa dei polinomi

Dato che la complessità è spesso correlata agli algoritmi divide et impera, O(log(n)) è generalmente una buona complessità da raggiungere con gli algoritmi di ordinamento. O(log(n)) è meno complessa di O(√n), perché la radice quadrata può essere considerata polinomiale, dove l'esponente è 0.5.

3. La complessità dei polinomi cresce con il loro esponente

Ad esempio, O(n⁵) è più complessa di O(n⁴). Grazie a questa semplicità, abbiamo fatto svariati esempi di polinomi nelle sezioni precedenti.

4. Le funzioni esponenziali hanno una complessità maggiore delle polinomiali finché i coefficienti sono multipli positivi di n

O(2ⁿ) è più complesso di O(n⁹⁹), ma O(2ⁿ) è meno complesso di O(1). Generalmente, prendiamo 2 come base per gli esponenziali e i logaritmi perché le cose tendono a essere binarie in informatica, ma gli esponenti possono essere cambiati variando i coefficienti. Quando non specificato, la base dei logaritmi è 2.

5. I fattoriali hanno una complessità maggiore delle esponenziali

Se ti interessa il ragionamento, dai un'occhiata alla funzione gamma, una continuazione analitica di un fattoriale. Una breve dimostrazione è che sia fattoriali che esponenziali hanno lo stesso numero di moltiplicazioni, ma il numero che viene moltiplicato cresce per i fattoriali, mentre rimane costante per gli esponenziali.

6. Moltiplicare i termini

Moltiplicando, la complessità sarà maggiore di quella originale, ma non più grande del prodotto ottenuto moltiplicando qualcosa di più complesso. Ad esempio, O(n * log(n)) è più complessa di O(n) ma meno complessa di O(n²), perché O(n²) = O(n * n) e n è più complessa di log(n).

Per metterti alla prova, cerca di ordinare le seguenti funzioni dalla più complessa alla meno complessa. Continuando a leggere potrai trovare la soluzione con spiegazioni dettagliate in una sezione successiva. Alcune sono scelte per essere ingannevoli e potrebbero richiedere conoscenze matematiche approfondite. Man mano che ti avvicini alla soluzione capirai meglio.

Domanda: ordina le seguenti funzioni dalla più complessa alla meno complessa.

Soluzione alla domanda della sezione 2:

Era volontariamente ideata in modo da essere una domanda insidiosa per metterti alla prova. La domanda ti tenta a rispondere O(n²) perché c'è un loop annidato. Tuttavia, n è la dimensione dell'input. Dato che l'array dell'immagine è l'input e il loop itera su ogni pixel solo una volta, la risposta in realtà è O(n). Nella prossima sezione ci saranno più esempi come questo.

5. Complessità temporale & spaziale

Finora, abbiamo parlato solo della complessità temporale degli algoritmi, ovvero ci siamo interessati solo al tempo che impiega il programma per completare l'attività. Ma ciò che conta è anche lo spazio che il programma necessita per completare l'attività. La complessità spaziale è correlata a quanta memoria userà il programma, dunque un altro fattore importante da analizzare.

La complessità spaziale funziona in modo simile alla complessità temporale. Ad esempio, selection sort ha una complessità spaziale di O(1), perché memorizza soltanto un valore minimo e il suo indice come confronto, e lo spazio massimo utilizzato non cresce con la dimensione dell'input.

Alcuni algoritmi, come bucket sort, hanno una complessità spaziale di O(n), ma sono in grado di ridurre la complessità temporale fino a O(1). Bucket sort ordina l'array creando una lista ordinata di tutti i possibili elementi nell'array, poi incrementa il conteggio ogni volta che incontra un elemento. Alla fine, l'array ordinato sarà la lista ordinata di elementi ripetuti a seconda del loro conteggio.

6. Complessità attesa, caso migliore, medio e peggiore

La complessità può anche essere analizzata secondo caso migliore, peggiore, medio e caso atteso

Prendiamo come esempio insertion sort. L'algoritmo itera su tutti gli elementi nella lista. Se un elemento è minore del precedente, lo inserisce indietro, finché non è maggiore dell'elemento che lo precede.

Se l'array è inizialmente ordinato, non verrà effettuato nessuno scambio. L'algoritmo itererà semplicemente sugli elementi dell'array una volta, ottenendo una complessità di O(n). Dunque, possiamo dire che il caso migliore di complessità temporale di insertion sort è O(n). Una complessità di O(n) è spesso chiamata complessità lineare.

A volte un algoritmo è sfortunato. Quick sort, ad esempio, dovrà scorrere attraverso la lista in un tempo O(n) se gli elementi sono ordinati nel verso opposto, ma in media ordina un array in un tempo O(n * log(n)). Generalmente, quando valutiamo la complessità di un algoritmo, ci interessiamo alle prestazioni nel caso peggiore. Parleremo ancora di questo e di quick sort nella prossima sezione.

La complessità del caso medio descrive la prestazione attesa da un algoritmo. A volte implica il calcolo della probabilità di ogni situazione. Può diventare complicato addentrarsi nei dettagli e perciò non ne discuterò in questo articolo. Qui sotto puoi trovare uno specchietto riassuntivo sulle complessità spaziali e temporali di algoritmi tipici.

Soluzione alla domanda della sezione 4:

Analizzando le funzioni, dovremmo essere in grado di classificare immediatamente i seguenti polinomi dal più complesso al meno complesso con la regola 3. Dove la radice quadrata di n corrisponde semplicemente all'elevamento all'esponente 0.5.

Poi, applicando le regole 2 e 6, otteniamo quanto segue. Il logaritmo in base 3 può essere trasformato in base 2 con un cambiamento di base. Il logaritmo in base 3 cresce un po' più lentamente di quelli in base 2 e quindi viene posizionato dopo.

Il resto potrebbe sembrare un po' complicato, ma tentiamo di svelare l'arcano e vedere dove possiamo inserire le funzioni rimanenti.

Prima di tutto, 2 elevato a 2 alla n è maggiore di 2 alla n, e il +1 concorre a un aumento ulteriore.

E dato che sappiamo che 2 elevato a log(n) in base 2 è uguale a n, possiamo convertire le seguenti funzioni. Il logaritmo con esponente 0.001 cresce un po' di più di una costante, ma meno di quasi ogni altra cosa.

La funzione con n alla potenza di log(log(n)), in realtà è una variazione della quasi-polinomiale, che è maggiore della polinomiale ma minore dell'esponenziale. Dato che log(n) cresce più lentamente di n, la complessità è leggermente inferiore. La funzione con il reciproco del logaritmo converge a una costante, dato che 1/log(n) diverge verso infinito.

I fattoriali possono essere rappresentati con delle moltiplicazioni e quindi possono essere convertiti in addizioni fuori dalla funzione logaritmica. "n su 2" può essere convertito in un polinomio con il termine più grande cubico.

E finalmente, possiamo ordinare le funzioni dalla più complessa alla meno complessa.

Perché O grande non conta

!!! — ATTENZIONE — !!!

I contenuti discussi qui, non sono generalmente accettati dalla maggior parte dei programmatori nel mondo. Parlane a tuo rischio durante un colloquio. Alcune persone riportano che hanno fallito il loro colloquio di lavoro perché hanno messo in discussione l'autorità, come qui.

!!! — ATTENZIONE — !!!

Dato che abbiamo precedentemente imparato che il caso peggiore di complessità temporale per quick sort è O(n²), mentre per merge sort è O(n * log(n)), merge sort dovrebbe essere più veloce, vero? Hai probabilmente indovinato che la risposta è falso.

Per dimostrarlo, dai un'occhiata a questo trinket.io che ho realizzato. Confronta il tempo per quick sort e merge sort. L'ho testato solo su array con una lunghezza fino a 10000, ma come puoi vedere, il tempo per merge sort cresce più velocemente che per quick sort. Nonostante quick sort abbia una complessità nel caso peggiore di O(n²), la probabilità è davvero bassa. Quando si tratta dell'aumento di velocità, quick sort prevale su merge sort che è vincolato alla complessità O(n * log(n)), e quick sort finisce per avere delle prestazioni migliori in media.

Ho anche realizzato il grafico qui sotto per confrontare il rapporto tra il tempo che impiegano, dato che è difficile vedere i loro valori. Come puoi vedere, il tempo percentuale impiegato per quick sort è in ordine discendente.

La morale della favola è che la notazione O grande è solo un'analisi matematica per fornire un riferimento alle risorse richieste da un algoritmo. Nella pratica, i risultati possono essere differenti, ma in generale, è una buona pratica tentare di abbattere la complessità di un algoritmo, finché non ci imbattiamo in un caso in cui sappiamo cosa stiamo facendo.

In conclusione…

Mi piace programmare, imparare cose nuove e condividerle con la comunità. Se c'è qualcosa che ti interessa particolarmente, per favore, fammelo sapere. Generalmente scrivo di web design, architettura del software, matematica e scienza dei dati. Puoi trovare alcuni articoli validi che ho scritto in precedenza se sei interessato a questi argomenti.

Buon divertimento con lo studio dell'informatica!!!

Cosa sono gli algoritmi divide et impera?

Divide et impera è un paradigma algoritmico, simile al metodo Greedy o alla programmazione dinamica. Un tipico algoritmo divide et impera risolve problemi usando i tre step seguenti.

1. Divide: suddivisione del problema dato in sotto-problemi dello stesso tipo. I sotto-problemi dovrebbero essere parte del problema originario. Questo passaggio avviene con un approccio ricorsivo, dividendo il problema finché non è possibile una suddivisione ulteriore dei sotto-problemi. In questo stadio, i sotto-problemi non sono ulteriormente scindibili ma rappresentano ancora una parte del problema reale.
2. Impera: risoluzione ricorsiva dei sotto-problemi. Questo passaggio richiede di risolvere un numero elevato di sotto-problemi. Generalmente, a questo livello, i problemi vengono considerati risolti singolarmente.
3. Combina: combinazione appropriata delle risposte. Quando i sotto-problemi più piccoli sono risolti, vengono combinati ricorsivamente fino a formulare una soluzione del problema di partenza. Questo approccio algoritmico funziona ricorsivamente, e gli step impera e combina sono così vicini che appaiono come uno solo.

Questo metodo, di solito, ci permette di ridurre considerevolmente la complessità temporale.

Ad esempio, Bubble Sort ha una complessità di O(n2), mentre quicksort (un'applicazione di divide et impera) riduce la complessità temporale a O(nlog(n)). L'algoritmo di ricerca lineare ha una complessità temporale di O(n), mentre quello di ricerca binaria (un'applicazione di divide et impera) riduce la complessità temporale a O(log(n)).

Di seguito, sono elencati alcuni algoritmi standard del tipo divide et impera.

Ricerca binaria è un algoritmo di ricerca. In ogni step, l'algoritmo confronta l'elemento di input (x) con il valore al centro dell'array. Se i valori coincidono, allora l'algoritmo restituisce l'indice corrispondente. Altrimenti, se x è minore dell'elemento centrale, l'algoritmo passa al lato sinistro dell'elemento centrale. In caso contrario, passa al lato destro.

Quicksort è un algoritmo di ordinamento. L'algoritmo riordina gli elementi di un array in modo che tutti gli elementi più piccoli di un elemento, detto pivot, vengono spostati alla sinistra di quest'ultimo, e tutti quelli maggiori alla sua destra. Infine, l'algoritmo ordina ricorsivamente i sotto-array a sinistra e a destra del pivot.

Merge Sort è un altro algoritmo di ordinamento. L'algoritmo divide l'array in due metà e le ordina ricorsivamente, per poi unire le due metà ordinate. La complessità temporale è O(nLogn), che sia il caso migliore, medio o peggiore. La sua complessità può essere compresa facilmente dato che la ricorrenza è: T(n) = 2T(n/2) + n.

Coppia di punti più vicini. Il problema è trovare la coppia di punti più vicini tra un insieme di punti in un piano x-y e può essere risolto in un tempo O(n2), calcolando le distanze di ogni coppia di punti e confrontando le distanze per trovare quella minore. L'algoritmo divide et impera risolve il problema in un tempo O(nLogn).

L'algoritmo di Strassen è un efficiente algoritmo per moltiplicare matrici. Un metodo semplice per moltiplicare due matrici necessita di 3 loop annidati e di un tempo O(n3). L'algoritmo di Strassen moltiplica due matrici in un tempo O(n2.8974).

L'algoritmo di Cooley–Tukey a trasformata di Fourier veloce (FFT) è l'algoritmo FFT più comune. È un algoritmo divide et impera che opera in un tempo O(nlogn).

L'algoritmo di Karatsuba è stato il primo algoritmo di moltiplicazione asintoticamente più veloce degli algoritmi quadratici. Riduce la moltiplicazione di due numeri a n cifre al massimo a n^1.585 (approssimativamente log2(3)) moltiplicazioni a una cifra. È quindi pià veloce dell'algoritmo classico, il quale richiede n² algoritmi a una cifra.

Divide et impera vs programmazione dinamica

Entrambi i paradigmi (divide et impera e programmazione dinamica) dividono un dato problema in sotto-problemi e risolvono i sotto-problemi. Come scegliere tra i due? Divide et impera dovrebbe essere utilizzato quando gli stessi sotto-problemi non vengono valutati molte volte. Altrimenti dovrebbe essere usata la programmazione dinamica o la memoizzazione.

Ad esempio, l'algoritmo di ricerca binaria è un algoritmo divide et impera, in cui non viene mai rivalutato lo stesso sotto-problema. Invece, per calcolare l'n-esimo numero di Fibonacci, è da preferire la programmazione dinamica.

Cos'è un algoritmo di ordinamento?

Gli algoritmi di ordinamento sono un insieme di istruzioni che prendono un array o una lista come input e ne riorganizzano gli elementi in un ordine particolare.

I più comuni operano in ordine numerico o in una forma di ordine alfabetico (lessicografico) e possono ordinare in modo ascendente (A-Z, 0-9) o discendente (Z-A, 9-0).

Perché gli algoritmi di ordinamento sono importanti?

Dato che spesso sono in grado di ridurre la complessità di un problema, gli algoritmi di ordinamento sono estremamente importanti in informatica. Questi algoritmi hanno applicazioni dirette in algoritmi di ricerca, algoritmi di database, metodi divide et impera, algoritmi di strutture dati e molti altri.

Pro e contro degli algoritmi di ordinamento

Nello scegliere un algoritmo di ordinamento, occorre che ci poniamo qualche domanda. Quanto è grande l'insieme da ordinare? Quanta memoria è disponibile? Dobbiamo aggiungere altri dati in futuro?

Le risposte a queste domande possono determinare quale algoritmo si adatterà al meglio a ogni situazione. Alcuni algoritmi, come il merge sort, possono richiedere molto spazio o memoria per essere eseguiti, mentre l'insertion sort non è sempre il più rapido, ma non necessita di molte risorse per essere eseguito.

Dovresti determinare quali sono i requisiti nel tuo caso e considerare le limitazioni del tuo sistema prima di decidere quale algoritmo di ordinamento usare.

Algoritmi di ordinamento comuni

Ecco alcuni dei più comuni algoritmi di ordinamento:

• Selection sort (ordinamento per selezione)
• Bubble sort (ordinamento a bolla)
• Insertion sort (ordinamento a inserimento)
• Merge sort
• Quick sort
• Heapsort (ordinamento per heap)
• Counting sort
• Radix sort
• Bucket sort

Ma prima di affrontarli uno per uno, parliamo un po' di come classificare gli algoritmi di ordinamento.

Classificazione degli algoritmi di ordinamento

Gli algoritmi di ordinamento possono essere categorizzati in base ai seguenti parametri:

1. Il numero richiesto di scambi o inversioni: è il numero di volte in cui l'algoritmo scambia gli elementi per riorganizzare l'input. Selection sort richiede il numero minimo di scambi.
2. Il numero di confronti: è il numero di volte che un algoritmo confronta gli elementi per riorganizzare l'input. Usando la notazione O-grande, gli algoritmi di ordinamento elencati precedentemente richiedono almeno O(nlogn) confronti nel caso migliore e O(n^2) confronti nel caso peggiore per la maggior parte degli output.
3. Fanno o non fanno uso della ricorsione:  alcuni algoritmi di ordinamento, come quick sort, usano tecniche ricorsive per ordinare l'input, Altri algoritmi di ordinamento, come selection sort o insertion sort, usano tecniche non ricorsive. Infine, alcuni come merge sort, usano sia tecniche ricorsive che non per ordinare l'input.
4. Sono stabili o instabili: gli algoritmi di ordinamento stabili mantengono l'ordine relativo degli elementi con valori o chiavi uguali. Quelli instabili non mantengono l'ordine relativo di elementi con valori/chiavi uguali.
   
   Ad esempio, immagina di avere l'array di input [1, 2, 3, 2, 4]. Per evidenziare la differenza tra i due valori uguali 2, denotiamoli con 2a e 2b, ottenendo l'array di input [1, 2a, 3, 2b, 4].
   
   Gli algoritmi di ordinamento stabili mantengono l'ordine di 2a e 2b, così che l'output sarà [1, 2a, 2b, 3, 4]. Quelli instabili non mantengono l'ordine dei valori uguali e l'array di output potrebbe essere [1, 2b, 2a, 3, 4].
   
   Insertion sort, merge sort e bubble sort sono stabili. Heap sort e quick sort sono instabili.
5. La quantità di spazio extra richiesto: alcuni algoritmi di ordinamento possono ordinare una lista senza crearne una nuova. Questi sono conosciuti come algoritmi di ordinamento in loco (o in place) e richiedono uno spazio di memoria extra costante O(1). Invece, gli algoritmi di ordinamento non in loco creano una nuova lista ordinando l'input.
   
   Insertion sort e quick sort sono in loco, dato che gli elementi vengono spostati intorno a un elemento pivot e non fanno uso di un array separato.
   
   Merge sort è un esempio di ordinamento non in loco, dato che la dimensione dell'input viene assegnata in anticipo per contenere l'output durante il processo di ordinamento, richiedendo memoria aggiuntiva.

Bucket Sort

Bucket sort è un algoritmo di ordinamento che opera sugli elementi dividendoli in diversi bucket per poi ordinare individualmente i bucket. Ognuno di essi viene ordinato separatamente usando uno specifico algoritmo di ordinamento come insertion sort o applicando ricorsivamente bucket sort.

Bucket sort è principalmente utile quando l'input è uniformemente distribuito in un intervallo. Ad esempio, immagina di avere un grande array di numeri decimali distribuiti uniformemente tra un estremo inferiore e un estremo superiore.

Potresti utilizzare un altro algoritmo di ordinamento come merge sort o quick sort, tuttavia, questi algoritmi garantiscono nel caso migliore una complessità temporale di O(nlogn).

Usando bucket sort, l'ordinamento dello stesso array può avvenire in un tempo O(n).

Pseudo-codice per Bucket Sort:

funzione bucketSort(array di numeri a,intero n)
    per ogni numero intero x in n
        inserisci x in bucket[n*x]; 
    per ogni bucket
        ordina(bucket);

Counting Sort

L'algoritmo counting sort crea inizialmente una lista con il conteggio o le occorrenze di ogni valore unico nell'input, per poi generare la lista finale ordinata in base alla lista con le occorrenze.

Una cosa importante da tenere a mente è che counting sort può essere usato soltanto conoscendo a priori l'intervallo dei valori possibili.

Esempio:

Hai una lista di interi da 0 a 5:

input = [2, 5, 3, 1, 4, 2]

Hai bisogno di creare una lista con il conteggio di ogni valore unico nella lista input. Dato sai che l'intervallo dei valori di input è da 0 a 5, puoi creare una lista con 5 segnaposti per i valori da 0 a 5, rispettivamente:

count = [0, 0, 0, 0, 0, 0]
  # val: 0  1  2  3  4  5

Poi, percorri la lista input iterando sull'indice per ogni valore.

Ad esempio, il primo valore della lista input è 2, quindi aggiungi uno al valore al secondo indice della lista count list, che rappresenta il valore 2:

count = [0, 0, 1, 0, 0, 0]
  # val: 0  1  2  3  4  5

Il valore successivo nella lista input è 5, quindi aggiungi uno al valore all'ultimo indice della lista count, che rappresenta il valore 5:

count = [0, 0, 1, 0, 0, 1]
  # val: 0  1  2  3  4  5

Continui finché non hai il conteggio totale di ogni valore nella lista input:

count = [0, 1, 2, 1, 1, 1]
  # val: 0  1  2  3  4  5

Infine, dato che conosci quante volte appare ogni valore nella lista input, puoi creare facilmente una lista output ordinata. Itera sulla lista count e, per ogni conteggio, aggiungi il valore corrispondente
(0 - 5) all'array output quel numero di volte.

Ad esempio, non ci sono 0 nella lista input list, ma il valore 1 è presente una volta, quindi lo aggiungi all'array output una volta:

output = [1]

Il valore 2 è presente due volte, quindi lo aggiungi alla lista output due volte:

output = [1, 2, 2]

E così via, finché non ottieni la lista finale output ordinata:

output = [1, 2, 2, 3, 4, 5]

Proprietà

• Complessità spaziale: O(k)
• Performance nel caso migliore: O(n+k)
• Performance media: O(n+k)
• Performance nel caso peggiore: O(n+k)
• Stabile: sì (k è nell'intervallo degli elementi dell'array)

Implementazione in JavaScript

let numeri = [1, 4, 1, 2, 7, 5, 2];
let conteggio = [];
let output = [];
let i = 0;
let max = Math.max(...numeri);

// inizializza counter
for (i = 0; i <= max; i++) {
  conteggio[i] = 0;
}

// inizializza l'array output
for (i = 0; i < numeri.length; i++) {
  output[i] = 0;
}

for (i = 0; i < numeri.length; i++) {
  conteggio[numeri[i]]++;
}

for (i = 1; i < conteggio.length; i++) {
  conteggio[i] += conteggio[i - 1];
}

for (i = numeri.length - 1; i >= 0; i--) {
  output[--conteggio[numeri[i]]] = numeri[i];
}

// array output ordinato
for (i = 0; i < output.length; i++) {
  console.log(output[i]);
}

Implementazione in C++

#include <iostream>

#include <vector>

void countSort(int upperBound, int lowerBound, std::vector < int > numbersToSort) // limite inferiore (lowerBound) e superiore (upperBound) dei numeri in vector
{
  int i;
  int range = upperBound - lowerBound; // Crea un range largo abbastanza da contenere tutti i numeri tra il minimo e il massimo
  std::vector < int > counts(range + 1); // Inizializza counts della dimensione del range
  std::fill(counts.begin(), counts.end(), 0); // Riempi il vettore di zeri
  std::vector < int > storedNumbers(numbersToSort.size()); // Inizializza storedNumbers della stessa dimensione del vettore di input
  std::fill(storedNumbers.begin(), storedNumbers.end(), 0); // Riempi il vettore storedNumbers di zeri

  for (i = 0; i < numbersToSort.size(); i++) {
    int index = numbersToSort[i] - lowerBound; // For example, if 5 is the lower bound and numbersToSort[i] is 5, the inPer esempio, se 5 è il limite inferiore, e numbersToSort[i] è 5, l'indice sarà 0
    counts[index] += 1; // e il conteggio di 5 è salvato in counts[0]
  }

  for (i = 1; i < counts.size(); i++) {
    counts[i] += counts[i - 1];
  }

  for (i = numbersToSort.size() - 1; i >= 0; i--) { // Copia gli elementi da numbersToSort a storedNumbers seguento count
    storedNumbers[--counts[numbersToSort[i] - lowerBound]] = numbersToSort[i];
  }

  for (i = 0; i < storedNumbers.size(); i++) {
    std::cout << storedNumbers[i];
    if (i != storedNumbers.size() - 1)
      std::cout << ", ";
  }
  std::cout << std::endl;
}

Implementazione in Swift

func countingSort(_ array: [Int]) {
  // Crea un array per salvare il conteggio di ogni elemento
  let maxElement = array.max() ?? 0
  var countArray = [Int](repeating: 0, count: Int(maxElement + 1))

  for element in array {
    countArray[element] += 1
  }

  for i in 1..<countArray.count {
    countArray[i] += countArray[i - 1]
  }

  var sortedArray = [Int](repeating: 0, count: array.count)

  // copia gli elementi da array a sortedArray seguendo count
  for i in (0..<array.count).reversed() {
    countArray[array[i]] -= 1
    sortedArray[countArray[array[i]]] = array[i]
  }

  print(sortedArray)
}

Insertion Sort

Insertion sort è un semplice algoritmo di ordinamento adatto a un numero ridotto di elementi.

Esempio:

Insertion sort confronta l'elemento key con gli elementi precedenti. Se gli elementi precedenti sono più grandi dell'elemento key, vengono spostati nella posizione successiva.

Inizia dall'indice 1 fino alla lunghezza dell'array di input.

[ 8 3 5 1 4 2 ]

Step 1 :

key = 3 //partendo dal 1° indice.

key viene confrontato con gli elementi precedenti.

In questo caso, key viene confrontato con 8. Dato che 8 > 3, l'8 viene spostato nella posizione successiva e key inserita nella precedente.

Risultato: [ 3 8 5 1 4 2 ]

Step 2 :

      key = 5 //2° indice

      8 > 5 //sposta 8 al 2° indice e inserisce 5 al 1° indice.

      Risultato: [ 3 5 8 1 4 2 ]

Step 3 :

      key = 1 //3° indice

      8 > 1     => [ 3 5 1 8 4 2 ]  

      5 > 1     => [ 3 1 5 8 4 2 ]

      3 > 1     => [ 1 3 5 8 4 2 ]

      Risultato: [ 1 3 5 8 4 2 ]

Step 4 :

      key = 4 //4° indice

      8 > 4   => [ 1 3 5 4 8 2 ]

      5 > 4   => [ 1 3 4 5 8 2 ]

      3 > 4   ≠>  stop

      Risultato: [ 1 3 4 5 8 2 ]

Step 5 :

      key = 2 //5° indice

      8 > 2   => [ 1 3 4 5 2 8 ]

      5 > 2   => [ 1 3 4 2 5 8 ]

      4 > 2   => [ 1 3 2 4 5 8 ]

      3 > 2   => [ 1 2 3 4 5 8 ]

      1 > 2   ≠> stop

      Risultato: [1 2 3 4 5 8]

L'algoritmo mostrato qui sotto è una versione leggermente ottimizzata per evitare di scambiare l'elemento key in ogni iterazione. Qui, l'elemento key  verrà scambiato alla fine dell'iterazione (step).

    InsertionSort(arr[])
      for j = 1 to arr.length
         key = arr[j]
         i = j - 1
         while i > 0 and arr[i] > key
            arr[i+1] = arr[i]
            i = i - 1
         arr[i+1] = key

Ecco l'implementazione dettagliata in JavaScript:

function insertion_sort(A) {
    var len = array_length(A);
    var i = 1;
    while (i < len) {
        var x = A[i];
        var j = i - 1;
        while (j >= 0 && A[j] > x) {
            A[j + 1] = A[j];
            j = j - 1;
        }
        A[j + 1] = x;
        i = i + 1;
    }
}

E un'implementazione breve in Swift:

var array = [8, 3, 5, 1, 4, 2]

func insertionSort(array: inout [Int]) -> [Int] {
  for j in 0..<array.count {
    let key = array[j]
    var i = j - 1

    while i > 0 && array[i] > key {
      array[i + 1] = array[i]
      i = i - 1
    }
    array[i + 1] = key
  }
  return array
}

Qui sotto puoi vedere un esempio in Java:

public int[] insertionSort(int[] arr) {
    for (j = 1; j < arr.length; j++) {
        int key = arr[j]
        int i = j - 1
        while (i > 0 and arr[i] > key) {
            arr[i + 1] = arr[i]
            i -= 1
        }
        arr[i + 1] = key
    }
    return arr;
}

E infine in C:

void insertionSort(int arr[], int n) {
  int i, key, j;
  for (i = 1; i < n; i++) {
    key = arr[i];
    j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
}

Proprietà:

• Complessità spaziale: O(1)
• Complessità temporale: O(n), O(n* n), O(n* n) rispettivamente per caso migliore, media e caso peggiore.
• Caso migliore: l'array è già ordinato
• Media: l'array è ordinato in modo casuale
• Caso peggiore: l'array è ordinato è invertito.
• Ordinamento in loco: sì
• Stabile: sì

Heapsort

Heapsort è un efficiente algoritmo di ordinamento basato sull'uso di max/min heap. Un heap è una struttura di dati ad albero che soddisfa la proprietà di heap: per un max heap, la chiave di ogni nodo è minore o uguale alla chiave del suo genitore (se ne possiede uno).

Questa proprietà può essere sfruttata per accedere all'elemento massimo nell'heap in un tempo O(logn), usando il metodo maxHeapify. Svolgiamo questa operazione n volte, ogni volta muovendo il massimo in cima all'heap ed estraendolo per inserirlo nell'array ordinato. Dunque, dopo n iterazioni avremo una versione ordinata dell'array di input.

È un algoritmo in loco e richiede di costruire inizialmente una struttura di dati heap. L'algoritmo è anche instabile, che significa che in seguito al confronto di oggetti con la stessa chiave, l'ordine originale non viene preservato.

Questo algoritmo viene eseguito in un tempo O(nlogn) e spazio addizionale O(1)  (O(n) includendo lo spazio richiesto per memorizzare i dati di input) dato che tutte le operazioni vengono eseguite completamente in loco.

La complessità temporale di heapsort nel caso migliore, medio e peggiore è O(nlogn). Sebbene heapsort abbia una migliore complessità nel caso peggiore  rispetto a quicksort, in pratica, quicksort viene eseguito più velocemente se ben implemenetato. È un algortimo basato sul confronto, quindi può essere usato per insiemi di dati non numerici, in quanto una certa relazione (proprietà heap) può essere definita tra gli elementi.

Qui sotto puoi vedere l'implementazione in Java:

import java.util.Arrays;
public class Heapsort {

    public static void main(String[] args) {
        // array di test
        Integer[] arr = {
            1,
            4,
            3,
            2,
            64,
            3,
            2,
            4,
            5,
            5,
            2,
            12,
            14,
            5,
            3,
            0,
            -1
        };
        String[] strarr = {
            "hope you find this helpful!",
            "wef",
            "rg",
            "q2rq2r",
            "avs",
            "erhijer0g",
            "ewofij",
            "gwe",
            "q",
            "random"
        };
        arr = heapsort(arr);
        strarr = heapsort(strarr);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(strarr));
    }

    // TEMPO O(nlogn), SPAZIO O(1), NON STABOILE
    public static < E extends Comparable < E >> E[] heapsort(E[] arr) {
        int heaplength = arr.length;
        for (int i = arr.length / 2; i > 0; i--) {
            arr = maxheapify(arr, i, heaplength);
        }

        for (int i = arr.length - 1; i >= 0; i--) {
            E max = arr[0];
            arr[0] = arr[i];
            arr[i] = max;
            heaplength--;
            arr = maxheapify(arr, 1, heaplength);
        }

        return arr;
    }

    // Crea maxheap dall'array
    public static < E extends Comparable < E >> E[] maxheapify(E[] arr, Integer node, Integer heaplength) {
        Integer left = node * 2;
        Integer right = node * 2 + 1;
        Integer largest = node;

        if (left.compareTo(heaplength) <= 0 && arr[left - 1].compareTo(arr[node - 1]) >= 0) {
            largest = left;
        }
        if (right.compareTo(heaplength) <= 0 && arr[right - 1].compareTo(arr[largest - 1]) >= 0) {
            largest = right;
        }
        if (largest != node) {
            E temp = arr[node - 1];
            arr[node - 1] = arr[largest - 1];
            arr[largest - 1] = temp;
            maxheapify(arr, largest, heaplength);
        }
        return arr;
    }
}

E in C++:

#include <iostream>

using namespace std;
void heapify(int arr[], int n, int i) {
  int largest = i;
  int l = 2 * i + 1;
  int r = 2 * i + 2;
  if (l < n && arr[l] > arr[largest])
    largest = l;
  if (r < n && arr[r] > arr[largest])
    largest = r;
  if (largest != i) {
    swap(arr[i], arr[largest]);

    heapify(arr, n, largest);
  }
}

void heapSort(int arr[], int n) {

  for (int i = n / 2 - 1; i >= 0; i--)
    heapify(arr, n, i);

  for (int i = n - 1; i >= 0; i--) {

    swap(arr[0], arr[i]);

    heapify(arr, i, 0);
  }
}
void printArray(int arr[], int n) {
  for (int i = 0; i < n; ++i)
    cout << arr[i] << " ";
  cout << "\n";
}
int main() {
  int arr[] = {
    12,
    11,
    13,
    5,
    6,
    7
  };
  int n = sizeof(arr) / sizeof(arr[0]);

  heapSort(arr, n);

  cout << "Sorted array is \n";
  printArray(arr, n);
}

Radix sort

Prerequisito: Counting sort

Quick sort, merge sort e heapsort sono algoritmi di ordinamento basati sul confronto. Counting sort non lo è. Ha una complessità di O(n+k), dove k è l'elemento massimo dell'array di input. Quindi, se k è O(n), counting sort diventa un ordinamento lineare, che è preferibile rispetto aa algoritmi di ordinamento basati sul confronto che hanno complessità temporale O(nlogn).

L'idea è di estendere l'algoritmo counting sort per ottenere una migliore complessità temporale quando k tende a O(n^2). Da qui, l'idea di Radix Sort.

L'algoritmo:

Per ogni cifra i, dove i varia dalla cifra meno significativa alla più significativa di un numero, ordina l'array di input usando l'algoritmo counting sort secondo la cifra i-esima. Usiamo counting sort perché è stabile.

Consideriamo come esempio l'array di input:

10, 21, 17, 34, 44, 11, 654, 123

L'algoritmo ordinerà l'array di input secondo la cifra delle unità (quella meno significativa).

0: 10
1: 21 11
2:
3: 123
4: 34 44 654
5:
6:
7: 17
8:
9:

Così l'array diventa:

10, 21, 11, 123, 24, 44, 654, 17

Adesso, l'ordinamento avviene in base alla cifra delle decine:

0:
1: 10 11 17
2: 21 123
3: 34
4: 44
5: 654
6:
7:
8:
9:

L'array diventa:

10, 11, 17, 21, 123, 34, 44, 654

Infine, l'ordinamento avvien secondo la cifra delle centinaia (quella più significativa):

0: 010 011 017 021 034 044
1: 123
2:
3:
4:
5:
6: 654
7:
8:
9:

L'array diventa:

10, 11, 17, 21, 34, 44, 123, 654

ed è ordinato. Ecco come funziona quest'algoritmo.

Ecco un'implementazione in C:

void countsort(int arr[], int n, int place) {

  int i, freq[range] = {
    0
  }; //range for integers is 10 as digits range from 0-9
  int output[n];

  for (i = 0; i < n; i++)
    freq[(arr[i] / place) % range]++;

  for (i = 1; i < range; i++)
    freq[i] += freq[i - 1];

  for (i = n - 1; i >= 0; i--) {
    output[freq[(arr[i] / place) % range] - 1] = arr[i];
    freq[(arr[i] / place) % range]--;
  }

  for (i = 0; i < n; i++)
    arr[i] = output[i];
}

void radixsort(ll arr[], int n, int maxx) { //maxx is the maximum element in the array

  int mul = 1;
  while (maxx) {
    countsort(arr, n, mul);
    mul *= 10;
    maxx /= 10;
  }
}

Selection Sort

Selection sort è uno degli algoritmi di ordinamento più semplici. Questo algoritmo prende il nome dal modo in cui itera sull'array: seleziona l'elemento più piccolo attuale e lo mette al suo posto.

Vediamo come funziona:

1. Trova l'elemento più piccolo dell'array e lo scambia con il primo elemento.
2. Trova il secondo elemento più piccolo dell'array e lo scambia con il secondo elemento dell'array.
3. Trova il terzo elemento più piccolo dell'array e lo scambia con il terzo elemento dell'array.
4. Ripete il processo di trovare l'elemento più piccolo successivo e posizionarlo correttamente finché l'array non è completamente ordinato.

Ma come scriveresti il codice per trovare l'indice del secondo valore nell'array?

Un modo semplice è notare che il valore più piccolo è già stato scambiato e posizionato all'indice 0, quindi il problema si riduce alla ricerca dell'elemento più piccolo partendo dall'indice 1.

Il numero di confronti di chiavi di selection sort è pari a N(N − 1)/2.

Implementazione in C/C++

Il seguente programma in C++ contiene un'implementazione iterativa e ricorsiva dell'algoritmo selection sort. Entrambe le implementazioni sono invocate nella funzione main().

#include <iostream>

#include <string>

using namespace std;

template < typename T, size_t n >
  void print_array(T
    const ( & arr)[n]) {
    for (size_t i = 0; i < n; i++)
      std::cout << arr[i] << ' ';
    cout << "\n";
  }

int minIndex(int a[], int i, int j) {
  if (i == j)
    return i;
  int k = minIndex(a, i + 1, j);
  return (a[i] < a[k]) ? i : k;
}

void recurSelectionSort(int a[], int n, int index = 0) {
  if (index == n)
    return;
  int k = minIndex(a, index, n - 1);
  if (k != index)
    swap(a[k], a[index]);
  recurSelectionSort(a, n, index + 1);
}

void iterSelectionSort(int a[], int n) {
  for (int i = 0; i < n; i++) {
    int min_index = i;
    int min_element = a[i];
    for (int j = i + 1; j < n; j++) {
      if (a[j] < min_element) {
        min_element = a[j];
        min_index = j;
      }
    }
    swap(a[i], a[min_index]);
  }
}

int main() {
  int recurArr[6] = {
    100,
    35,
    500,
    9,
    67,
    20
  };
  int iterArr[5] = {
    25,
    0,
    500,
    56,
    98
  };

  cout << "Recursive Selection Sort" << "\n";
  print_array(recurArr); // 100 35 500 9 67 20
  recurSelectionSort(recurArr, 6);
  print_array(recurArr); // 9 20 35 67 100 500

  cout << "Iterative Selection Sort" << "\n";
  print_array(iterArr); // 25 0 500 56 98
  iterSelectionSort(iterArr, 5);
  print_array(iterArr); // 0 25 56 98 500
}

Implementazione in JavaScript

function selection_sort(A) {
  var len = A.length;
  for (var i = 0; i < len - 1; i = i + 1) {
    var j_min = i;
    for (var j = i + 1; j < len; j = j + 1) {
      if (A[j] < A[j_min]) {
        j_min = j;
      } else {}
    }
    if (j_min !== i) {
      swap(A, i, j_min);
    } else {}
  }
}

function swap(A, x, y) {
  var temp = A[x];
  A[x] = A[y];
  A[y] = temp;
}

Implementazione in Python

def seletion_sort(arr):
    if not arr:
        return arr
    for i in range(len(arr)):
        min_i = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_i]:
                min_i = j
        (arr[i], arr[min_i]) = (arr[min_i], arr[i])

Implementazione in Java

public void selectionsort(int array[]) {
    int n = array.length; // metodo per trovare la lunghezza di un array 
    for (int i = 0; i < n - 1; i++) {
        int index = i;
        int min = array[i]; // prende l'elemento minimo come elemento i-esimo dell'array
        for (int j = i + 1; j < n; j++) {
            if (array[j] < array[index]) {
                index = j;
                min = array[j];
            }
        }
        int t = array[index]; // scambia il posto degli elemento
        array[index] = array[i];
        array[i] = t;
    }
}

Implementazione in MATLAB

function [sorted] = selectionSort(unsorted)
    len = length(unsorted);
    for i = 1:1:len
        minInd = i;
        for j = i+1:1:len
           if unsorted(j) < unsorted(minInd) 
               minInd = j;
           end
        end
        unsorted([i minInd]) = unsorted([minInd i]);    
    end
    sorted = unsorted;
end

Proprietà

• Complessità spaziale:  O(n)
• Complessità temporale:  O(n^2)
• Ordinamento in loco:  sì
• Stabile:  No

Bubble Sort

Bubble sort è un semplice algoritmo che ordina una lista, permettendo sia ai valori alti che bassi di raggiungerne la cima. L'algoritmo percorre la lista e confronta i valori adiacenti, scambiandoli se non sono nell'ordine corretto.

La complessità nel caso peggiore è di O(n^2). Bubble sort è molto lento se comparato ad altri algoritmi di ordinamento come quick sort. Il lato positivo è che è uno degli algoritmi di ordinamento più facili da comprendere e scrivere da zero.

Da un punto di vista tecnico, bubble sort è adeguato per ordinare array di piccole dimensioni o se è necessario eseguire un algoritmo di ordinamento su un computer con risorse di memoria particolarmente ridotte.

Esempio:

Primo passagio della lista:

• Partendo da [4, 2, 6, 3, 9], l'algoritmo compara i primi due elementi nell'array, 4 e 2. Li scambia perché 2 < 4: [2, 4, 6, 3, 9]
• Confronta i due valori successivi, 4 and 6. Dato che 4 < 6, risultano già in ordine e l'algoritmo passa avanti: [2, 4, 6, 3, 9]
• I due valori successivi vengono scambiati perché 3 < 6: [2, 4, 3, 6, 9]
• Gli ultimi due valori, 6 e 9, sono già in ordine e l'algoritmo non li scambia.

Secondo passaggio della lista:

• 2 < 4, quindi non c'è bisogno di scambiare le posizioni: [2, 4, 3, 6, 9]
• L'algoritmo scambia i valori successivi perché 3 < 4: [2, 3, 4, 6, 9]
• Non c'è scambio per i valori successivi, in quanto 4 < 6: [2, 3, 4, 6, 9]
• E ancora, 6 < 9, quindi non avviene nessuno scambio: [2, 3, 4, 6, 9]

La lista adesso è ordinata, ma l'algoritmo bubble sort non se ne accorge. Invece, necessita di completare un altro passaggio completo della lista senza scambiare alcun valore per sapere che la lista è ordinata.

Terzo passaggio della lista:

• [2, 3, 4, 6, 9] => [2, 3, 4, 6, 9]
• [2, 3, 4, 6, 9] => [2, 3, 4, 6, 9]
• [2, 3, 4, 6, 9] => [2, 3, 4, 6, 9]
• [2, 3, 4, 6, 9] => [2, 3, 4, 6, 9]

Chiaramente, bubble sort è lontano dall'essere l'algoritmo di ordinamento più efficiente. Ad ogni modo, è semplice da capire e da mettere in pratica.

Proprietà

• Complessità spaziale: O(1)
• Performance nel caso migliore:`O(n)`
• Performance media: O(n*n)
• Performance nel caso peggiore: O(n*n)
• Stabile: sì

Esempio in JavaScript

let arr = [1, 4, 7, 45, 7, 43, 44, 25, 6, 4, 6, 9],
  sorted = false;

while (!sorted) {
  sorted = true;
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < arr[i - 1]) {
      let temp = arr[i];
      arr[i] = arr[i - 1];
      arr[i - 1] = temp;
      sorted = false;
    }
  }
}

Esempio in Java

public class BubbleSort {
    static void sort(int[] arr) {
        int n = arr.length;
        int temp = 0;
        for (int i = 0; i < n; i++) {
            for (int x = 1; x < (n - i); x++) {
                if (arr[x - 1] > arr[x]) {
                    temp = arr[x - 1];
                    arr[x - 1] = arr[x];
                    arr[x] = temp;
                }

            }
        }

    }
    public static void main(String[] args) {

        for (int i = 0; i < 15; i++) {
            int arr[i] = (int)(Math.random() * 100 + 1);
        }

        System.out.println("array before sorting\n");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        bubbleSort(arr);
        System.out.println("\n array after sorting\n");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

    }
}

Esempio in C++

// implementazione ricorsiva
void bubblesort(int arr[], int n) {
  if (n == 1) // caso base
    return;
  bool swap_flag = false;
  for (int i = 0; i < n - 1; i++) { // dopo questo passaggio l'elemento più grande è spostato alla posizione desiderata

    if (arr[i] > arr[i + 1]) {
      int temp = arr[i];
      arr[i] = arr[i + 1];
      arr[i + 1] = temp;
      swap_flag = true;
    }
  }
  // se non sono stati scambiati elementi nel loop, allora restituisci che l'array è ordinato
  if (swap_flag == false)
    return;
  bubblesort(arr, n - 1); // ricorsione per il resto dell'array
}

Esempio in Swift

func bubbleSort(_ inputArray: [Int]) -> [Int] {
  // assicurati che l'array di input ha più di un elemento

  guard inputArray.count > 1 else { return inputArray }
  // gli argomenti delle funzioni sono costandi di default, quindi facciamo una copia
  var numbers = inputArray
  for i in 0..<(numbers.count - 1) {
    for j in 0..<(numbers.count - i - 1) {
      if numbers[j] > numbers[j + 1] {
        numbers.swapAt(j, j + 1)
      }
    }
  }
  // restituisce l'array ordinato
  return numbers
}

Esempio in Python

def bubbleSort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                (arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
    print arr

Esempio in PHP

function bubble_sort($arr) {
    $size = count($arr)-1;
    for ($i=0; $i<$size; $i++) {
        for ($j=0; $j<$size-$i; $j++) {
            $k = $j+1;
            if ($arr[$k] < $arr[$j]) {
                // Scambia elementi agli indici: $j, $k
                list($arr[$j], $arr[$k]) = array($arr[$k], $arr[$j]);
            }
        }
    }
    return $arr; // restituisci l'array ordinato
}

$arr = array(1,3,2,8,5,7,4,0);
print("Prima di ordinare");
print_r($arr);

$arr = bubble_sort($arr);
print("Dopo aver ordinato usando Bubble Sort");
print_r($arr);

Esempio in C

#include <stdio.h>

int BubbleSort(int array[], int n);

int main(void) {
  int arr[] = {
    10,
    2,
    3,
    1,
    4,
    5,
    8,
    9,
    7,
    6
  };
  BubbleSort(arr, 10);

  for (int i = 0; i < 10; i++) {
    printf("%d", arr[i]);
  }
  return 0;
}
int BubbleSort(int array[], n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) //n is length of array
    {
      if (array[j] > array[j + 1]) // For decreasing order use 
      {
        int swap = array[j];
        array[j] = array[j + 1];
        array[j + 1] = swap;
      }
    }
  }
}

Quick Sort

Quick sort è un efficiente algoritmo di ordinamento divide et impera. La sua complessità temporale nel caso medio è O(nlog(n)), mentre quella nel caso peggiore è O(n^2) in base alla selezione dell'elemento pivot, che divide l'array attuale in due sotto-array.

Ad esempio, la complessità temporale di quick sort è approssimativamente O(nlog(n)) quando la selezione del pivot divide l'array originale in due sotto-array di dimensione quasi uguale.

D'altra parte, se  l'algoritmo che seleziona l'elemento pivot dell'array di input restituisce costantemente 2 sotto-array con una grande differenza in termini di dimensione, l'algoritmo quick sort può raggiungere la complessità temporale del caso peggiore pari a O(n^2).

Gli step coinvolti in quick sort sono:

• Scelta dell'elemento pivot, in questo caso, l'ultimo elemento dell'array.
• Partizione: ordinamento dell'array in modo che tutti gli elementi minori del pivot siano a sinistra e tutti quelli maggiori a destra.
• Chiamata ricorsiva di quick sort, considerando il pivot precedente per dividere in modo adeguato gli array di sinistra e destra (Una discussione più dettagliata è presente nei commenti qui sotto).

Implementazione in JavaScript:

const arr = [6, 2, 5, 3, 8, 7, 1, 4];
const quickSort = (arr, start, end) => {
  if (start < end) {
    // puoi imparare come viene selezionato il pivot nei commenti sotto
    let pivot = partition(arr, start, end);
    // assicurati di leggere i conmmenti sotto per capire perché pivot-1 e pivot+1 sono usati
    // queste sono le invocazioni ricorsive a quickSort
    quickSort(arr, start, pivot - 1);
    quickSort(arr, pivot + 1, end);
  }
}
const partition = (arr, start, end) => {
  let pivot = end;
  // imposta i a start-1 così che possa accedere al primo indice nel caso in cui il valore di arr[0] sia più grande di arr[pivot]
  // i commenti successivi espandono sul commento qua sopra
  let i = start - 1,
    j = start;
  // incrementa j fino all'indice precedente il pivot
  while (j < pivot) {
    // se il valore è più grande del pivot allora incrementa j
    if (arr[j] > arr[pivot]) {
      j++;
    }
    // quando il valore ad arr[j] è minore del pivot:
    // incrementa i (arr[i] sarà un valore più grande di arr[pivot]) scambia i calori arr[i] e arr[j]
    else {
      i++;
      swap(arr, j, i);
      j++;
    }
  }
  // il valore ad arr[i+1] sarà più grande del valore ad arr[pivot]
  swap(arr, i + 1, pivot);
  /* restituisci i+1, visto che i valori alla sua sinistra sono inferiori ad arr[i+1]
     e i valore alla sua destra sono maggiorni di arr[i+1] */
  /* In questo modo, quando i quickSort ricorsivi sono chiamati,
     il nuovo sotto-array non include il valore pivot usato in precedenza */
  return i + 1;
}
const swap = (arr, firstIndex, secondIndex) => {
  let temp = arr[firstIndex];
  arr[firstIndex] = arr[secondIndex];
  arr[secondIndex] = temp;
}
quickSort(arr, 0, arr.length - 1);
console.log(arr);

Implementazione in C

#include<stdio.h>

void swap(int * a, int * b) {
  int t = * a;
  * a = * b;
  * b = t;
}
int partition(int arr[], int low, int high) {
  int pivot = arr[high];
  int i = (low - 1);

  for (int j = low; j <= high - 1; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap( & arr[i], & arr[j]);
    }
  }
  swap( & arr[i + 1], & arr[high]);
  return (i + 1);
}
void quickSort(int arr[], int low, int high) {
  if (low < high) {
    int pi = partition(arr, low, high);

    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}

void printArray(int arr[], int size) {
  int i;
  for (i = 0; i < size; i++)
    printf("%d ", arr[i]);
  printf("n");
}

int main() {
  int arr[] = {
    10,
    7,
    8,
    9,
    1,
    5
  };
  int n = sizeof(arr) / sizeof(arr[0]);
  quickSort(arr, 0, n - 1);
  printf("Sorted array: n");
  printArray(arr, n);
  return 0;
}

Implementazione in Python3

import random

z = [random.randint(0, 100) for i in range(0, 20)]


def quicksort(z):
    if len(z) > 1:
        piv = int(len(z) / 2)
        val = z[piv]
        lft = [i for i in z if i < val]
        mid = [i for i in z if i == val]
        rgt = [i for i in z if i > val]

        res = quicksort(lft) + mid + quicksort(rgt)
        return res
    else:
        return z


ans1 = quicksort(z)
print ans1

Implementazione in MATLAB

a = [9,4,7,3,8,5,1,6,2];

sorted = quicksort(a,1,length(a));

function [unsorted] =  quicksort(unsorted, low, high)
    if low < high
        [pInd, unsorted] = partition(unsorted, low, high);
        unsorted = quicksort(unsorted, low, pInd-1);
        unsorted = quicksort(unsorted, pInd+1, high);
    end

end

function [pInd, unsorted] = partition(unsorted, low, high)
    i = low-1;
    for j = low:1:high-1
        if unsorted(j) <= unsorted(high)
            i = i+1;
            unsorted([i,j]) = unsorted([j,i]);
            
        end
    end
    unsorted([i+1,high]) = unsorted([high,i+1]);
    pInd = i+1;

end

Complessità

Le complessità nel caso migliore, medio, peggiore e di memoria sono rispettivamente: n log(n), n log(n), n^2, log(n). Non è un algoritmo stabile ed è di solito eseguito in loco con O(log(n)) spazio di stack.

La complessità spaziale di quick sort è O(n). Rappresenta un miglioramento rispetto ad altri algoritmi di ordinamento divide et impera, che prendono uno spazio di O(nlog(n)).

Per quick sort, ciò avviene cambiando l'ordine degli elementi all'interno dell'array dato. Fai il confronto con merge sort, che crea 2 array, ognuno di lunghezza n/2 in ogni chiamata di funzione.

Tuttavia, se il pivot viene mantenuto nel mezzo, questi algoritmi di ordinamento vengono eseguiti in O(n*n). Si può evitare questo problema usando un pivot random.

Timsort

Timsort è un algoritmo di ordinamento veloce che opera in modo stabile con complessità O(N log(N)).

Timsort è un mix di insertion sort e merge sort. Questo algoritmo è implementato in Arrays.sort() di Java, ma anche sorted() e sort() in Python. Le parti più piccole vengono ordinate usando insertion sort e poi unite insieme con merge sort.

Implementazione in Python:

def binary_search(
    the_array,
    item,
    start,
    end,
    ):
    if start == end:
        if the_array[start] > item:
            return start
        else:
            return start + 1
    if start > end:
        return start

    mid = round((start + end) / 2)

    if the_array[mid] < item:
        return binary_search(the_array, item, mid + 1, end)
    elif the_array[mid] > item:

        return binary_search(the_array, item, start, mid - 1)
    else:

        return mid


def insertion_sort(the_array):
    l = len(the_array)
    for index in range(1, l):
        value = the_array[index]
        pos = binary_search(the_array, value, 0, index - 1)
        the_array = the_array[:pos] + [value] + the_array[pos:index] \
            + the_array[index + 1:]
    return the_array


def merge(left, right):
    """Prende due liste ordinare
    e restituisce una singola lista ordinata
    comparando gli elementi uno alla volta.
    [1, 2, 3, 4, 5, 6]
    """

    if not left:
        return right
    if not right:
        return left
    if left[0] < right[0]:
        return [left[0]] + merge(left[1:], right)
    return [right[0]] + merge(left, right[1:])


def timsort(the_array):
    (runs, sorted_runs) = ([], [])
    length = len(the_array)
    new_run = [the_array[0]]

    # per ogni i nel range da 1 alla lunghezza dell'array
    for i in range(1, length):

		# se i è alla fine della lista
        if i == length - 1:
            new_run.append(the_array[i])
            runs.append(new_run)
            break

		# se l'i-esimo elemento dell'aray è inferiore a quello prima
        if the_array[i] < the_array[i - 1]:

			# se new_run ha valore di None (NULL)
            if not new_run:
                runs.append([the_array[i]])
                new_run.append(the_array[i])
            else:
                runs.append(new_run)
                new_run = []
        else:

		# altrimenti se è uguare a maggiore di 
            new_run.append(the_array[i])

	# per ogni item in runs, appendilo usando insertion sort
    for item in runs:
        sorted_runs.append(insertion_sort(item))

	# per ogni run in sorted_runs, uniscile
    sorted_array = []
    for run in sorted_runs:
        sorted_array = merge(sorted_array, run)

    print sorted_array


timsort([
    2,
    3,
    1,
    5,
    6,
    7,
    ])

Complessità:

Timsort ha una complessità stabile di O(N log(N)) ed è ben comparabile con quick sort. Puoi vedere un confronto tra le complessità in questa tabella.

Merge Sort

Merge sort è un algoritmo divide et impera. Divide l'array di input in due metà, chiama sé stesso per le due metà e unisce le due porzioni ordinate. La porzione maggiore dell'algoritmo riceve due array ordinati, da unire in un singolo array ordinato. L'intero procedimento di ordinamento di un array di N interi può essere riassunto in 3 step:

• Divisione dell'array in due metà.
• Ordinamento della metà di sinistra e della metà di destra usando ricorsivamente lo stesso algoritmo.
• Unione delle due metà ordinate.

Esiste un algoritmo detto Two Finger che ci aiuta a unire assieme due array ordinati. Usando questo sottoprogramma e chiamando la funzione merge sort sulle metà dell'array ricorsivamente, otterremo l'array finale ordinato che stiamo cercando.

Dato che questo è un algoritmo basato sulla ricorsione, presenta una relazione di ricorrenza. La relazione di ricorrenza è semplicemente un modo di rappresentare  un problema in termini dei suoi sottoproblemi.

T(n) = 2 * T(n / 2) + O(n)

Traducendo in italiano: dividiamo il sottoproblema in due parti ad ogni step, e abbiamo una quantità lineare di operazioni da svolgere per unire le due metà ordinate in ogni step.

Complessità

Il vantaggio più grande dell'uso di merge sort è che la complessità temporale per l'ordinamento di un intero array è solamente n*log(n), molto meglio di n^2 per bubble sort o insertion sort.

Prima di scrivere il codice, vediamo di capire come funziona merge sort con l'aiuto di un diagramma.

• Inizialmente abbiamo un array di 6 interi non ordinati: Arr(5, 8, 3, 9, 1, 2)
• Dividiamo l'array in due metà Arr1 = (5, 8, 3) e Arr2 = (9, 1, 2)
• Di nuovo, li dividiamo in due metà: Arr3 = (5, 8) e Arr4 = (3) e Arr5 = (9, 1) e Arr6 = (2)
• Di nuovo, li dividiamo in due metà: Arr7 = (5), Arr8 = (8), Arr9 = (9), Arr10 = (1) and Arr6 = (2)
• Confrontiamo gli elementi nei sotto-array per poi unirli.

Proprietà:

• Complessità spaziale: O(n)
• Complessità temporale: O(n*log(n)). La complessità temporale per merge sort potrebbe non essere ovvia di primo acchito. Il fattore log(n) deriva dalla relazione di ricorrenza che abbiamo menzionato precedentemente.
• Ordinamento in loco: no, in una implementazione usuale.
• Stabile: sì.
• Parallelizzabile: sì (svariate varianti parallele sono discusse nella terza edizione di Introduction to Algorithms di Cormen, Leiserson, Rivest e Stein).

Implementazione in C++

void merge(int array[], int left, int mid, int right) {
  int i, j, k;

  // dimensione della sotto-lista sinistra 
  int size_left = mid - left + 1;

  // dimensione della sotto-lista denstra
  int size_right = right - mid;

  // crea gli array temporanei
  int Left[size_left], Right[size_right];

  // copia i dati agli array temporanei destro e sinistro
  for (i = 0; i < size_left; i++) {
    Left[i] = array[left + i];
  }

  for (j = 0; j < size_right; j++) {
    Right[j] = array[mid + 1 + j];
  }

  // unisci gli array temporanei in arr[left ..right]
  i = 0; // Indice iniziale del sotto-array sinistro
  j = 0; // Indice iniziare del sotto-array destro
  k = left; // Indice iniziare del sotto-array unito

  while (i < size_left && j < size_right) {
    if (Left[i] <= Right[j]) {
      array[k] = Left[i];
      i++;
    } else {
      array[k] = Right[j];
      j++;
    }
    k++;
  }

  // copia gli elementi rimanenti del sotto-array sinistro
  while (i < size_left) {
    array[k] = Left[i];
    i++;
    k++;
  }

  // copia gli elementi rimanenti del sotto-array destro
  while (j < size_right) {
    array[k] = Right[j];
    j++;
    k++;
  }
}

void mergeSort(int array[], int left, int right) {
  if (left < right) {
    int mid = (left + right) / 2;

    mergeSort(array, left, mid);
    mergeSort(array, mid + 1, right);

    // infine uniscili
    merge(array, left, mid, right);
  }
}

Implementazione in JavaScript

function mergeSort(arr) {
	if (arr.length < 2) return arr;
	var mid = Math.floor(arr.length / 2);
	var subLeft = mergeSort(arr.slice(0, mid));
	var subRight = mergeSort(arr.slice(mid));
	return merge(subLeft, subRight);
}

Prima verifichiamo la lunghezza dell'array. Se è 1, restituiamo semplicemente l'array. Questo è il caso base. Altrimenti, troviamo il valore centrale e dividiamo l'array in due metà. Ordiniamo entrambe le metà con chiamate ricorsive della funzione mergeSort.

function merge (a,b) {
    var result = [];
    while (a.length >0 && b.length >0)
        result.push(a[0] < b[0]? a.shift() : b.shift());
    return result.concat(a.length? a : b);
}

Quando uniamo le due metà, memorizziamo il risultato in un array ausiliario. Confronteremo l'elemento iniziale dell'array di sinistra con l'elemento iniziale dell'array di destra. Qualsiasi sia il minore, verrà inserito nell'array con il risultato e rimosso da quello d'appartenenza con l'operatore shift(). Se alla fine ci sono ancora valori negli array di sinistra o destra, verranno concatenati alla fine del risultato. Ecco l'array ordinato:

var test = [5, 6, 7, 3, 1, 3, 15];
console.log(mergeSort(test));

>> [1, 3, 3, 5, 6, 7, 15]

Implementazione in JS

const list = [23, 4, 42, 15, 16, 8, 3]

const mergeSort = (list) => {
	if (list.length <= 1) return list;
	const middle = list.length / 2;
	const left = list.slice(0, middle);
	const right = list.slice(middle, list.length);
	return merge(mergeSort(left), mergeSort(right));
}

const merge = (left, right) => {
	var result = [];
	while (left.length || right.length) {
		if (left.length && right.length) {
			if (left[0] < right[0]) {
				result.push(left.shift())
			} else {
				result.push(right.shift())
			}
		} else if (left.length) {
			result.push(left.shift())
		} else {
			result.push(right.shift())
		}
	}
	return result;
}

console.log(mergeSort(list)) // [ 3, 4, 8, 15, 16, 23, 42 ]

Implementazione in C

#include<stdlib.h>

#include<stdio.h>

void merge(int arr[], int l, int m, int r) {
  int i, j, k;
  int n1 = m - l + 1;
  int n2 = r - m;

  int L[n1], R[n2];

  for (i = 0; i < n1; i++)
    L[i] = arr[l + i];
  for (j = 0; j < n2; j++)
    R[j] = arr[m + 1 + j];
  i = 0;
  j = 0;
  k = l;
  while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
      arr[k] = L[i];
      i++;
    } else {
      arr[k] = R[j];
      j++;
    }
    k++;
  }

  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }

  while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
  }
}

void mergeSort(int arr[], int l, int r) {
  if (l < r) {
    int m = l + (r - l) / 2;

    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);

    merge(arr, l, m, r);
  }
}
void printArray(int A[], int size) {
  int i;
  for (i = 0; i < size; i++)
    printf("%d ", A[i]);
  printf("\n");
}
int main() {
    int arr[] = {
      12,
      11,
      13,
      5,
      6,
      7
    };
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;

Implementazione in C++

Consideriamo l'array A = {2,5,7,8,9,12,13} e l'array B = {3,5,6,9,15}. Vogliamo che anche l'array C sia in ordine ascendente.

void mergesort(int A[], int size_a, int B[], int size_b, int C[]) {
  int token_a, token_b, token_c;
  for (token_a = 0, token_b = 0, token_c = 0; token_a < size_a && token_b < size_b;) {
    if (A[token_a] <= B[token_b])
      C[token_c++] = A[token_a++];
    else
      C[token_c++] = B[token_b++];
  }

  if (token_a < size_a) {
    while (token_a < size_a)
      C[token_c++] = A[token_a++];
  } else {
    while (token_b < size_b)
      C[token_c++] = B[token_b++];
  }

}

Implementazione in Python

#!/usr/bin/python
# -*- coding: utf-8 -*-


def merge(left, right, compare):
    result = []
    (i, j) = (0, 0)
    while i < len(left) and j < len(right):
        if compare(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while i < len(left):
        result.append(left[i])
        i += 1
    while j < len(right):
        result.append(right[j])
        j += 1
    return result


def merge_sort(arr, compare=lambda x, y: x < y):

    # Usa funzione lambda per ordinare l'array in entrambi (crescente e decrescente) gli ordini
    # Come default ordina l'array in ordine crescente

    if len(arr) < 2:
        return arr[:]
    else:
        middle = len(arr) // 2
        left = merge_sort(arr[:middle], compare)
        right = merge_sort(arr[middle:], compare)
        return merge(left, right, compare)


arr = [2, 1, 4, 5, 3]
print merge_sort(arr)

Implementazione in Java

public class mergesort {

    public static int[] mergesort(int[] arr, int lo, int hi) {

        if (lo == hi) {
            int[] ba = new int[1];
            ba[0] = arr[lo];
            return ba;
        }

        int mid = (lo + hi) / 2;
        int arr1[] = mergesort(arr, lo, mid);
        int arr2[] = mergesort(arr, mid + 1, hi);
        return merge(arr1, arr2);
    }

    public static int[] merge(int[] arr1, int[] arr2) {
        int i = 0, j = 0, k = 0;
        int n = arr1.length;
        int m = arr2.length;
        int[] arr3 = new int[m + n];
        while (i < n && j < m) {
            if (arr1[i] < arr2[j]) {
                arr3[k] = arr1[i];
                i++;
            } else {
                arr3[k] = arr2[j];
                j++;
            }
            k++;
        }

        while (i < n) {
            arr3[k] = arr1[i];
            i++;
            k++;
        }

        while (j < m) {
            arr3[k] = arr2[j];
            j++;
            k++;
        }

        return arr3;

    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int arr[] = {
            2,
            9,
            8,
            3,
            6,
            4,
            10,
            7
        };
        int[] so = mergesort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++)
            System.out.print(so[i] + " ");
    }

}

Esempio in Java

public class mergesort {
    public static int[] mergesort(int[] arr, int lo, int hi) {
        if (lo == hi) {
            int[] ba = new int[1];
            ba[0] = arr[lo];
            return ba;
        }
        int mid = (lo + hi) / 2;
        int arr1[] = mergesort(arr, lo, mid);
        int arr2[] = mergesort(arr, mid + 1, hi);
        return merge(arr1, arr2);
    }

    public static int[] merge(int[] arr1, int[] arr2) {
        int i = 0, j = 0, k = 0;
        int n = arr1.length;
        int m = arr2.length;
        int[] arr3 = new int[m + n];
        while (i < n && j < m) {
            if (arr1[i] < arr2[j]) {
                arr3[k] = arr1[i];
                i++;
            } else {
                arr3[k] = arr2[j];
                j++;
            }
            k++;
        }
        while (i < n) {
            arr3[k] = arr1[i];
            i++;
            k++;
        }
        while (j < m) {
            arr3[k] = arr2[j];
            j++;
            k++;
        }
        return arr3;
    }

    public static void main(String[] args) {
        int arr[] = {
            2,
            9,
            8,
            3,
            6,
            4,
            10,
            7
        };
        int[] so = mergesort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++)
            System.out.print(so[i] + " ");
    }
}

Il cifrario di Cesare è una famosa attuazione della crittografia risalente ai suoi primordi. Prende una frase e la riorganizza, basandosi su una chiave che viene adoperata sull'alfabeto. Ad esempio, considera la chiave 3 e la frase

Mi piace indossare i cappelli.

Quando la frase viene codificata usando la chiave 3, diventa:

Pl sldfh lqgrvvduh l fdsshool.

In questo modo, è difficile leggere il messaggio, che può passare inosservato.

Mentre questo è un esempio di codifica m0lto semplice, è un progetto perfetto su cui far pratica per chi sta imparando a programmare.

Comprendere il cifrario

Per implementare questo codice, almeno in Java, avrai bisogno di riflettere a fondo su ciò che è stato fatto. Quindi, vediamo quali sono i passaggi fondamentali da considerare per questo codice.

Step 1: identifica il carattere nella frase.

Step 2: trova la posizione del carattere nell'alfabeto.

Step 3: identifica la somma di posizione del carattere + posizione della chiave nell'alfabeto.

Note* se la posizione del carattere + chiave > 26, torna indietro e ricomincia a contare da 1.

Step 4: costruisci una nuova frase usando i nuovi caratteri al posto di quelli originali.

Step 5: ripeti fino a raggiungere la lunghezza della frase (loop for).

Step 6: restituisci il risultato.

Codificare il cifrario

Questi sono dei buoni step da seguire, ma dovremmo pensare a cosa ci serve fare in termini di codice.

Step 0: crea una funzione che accetta un messaggio e una chiave.

Qualcosa del genere:

public String Encrypt(String message, int key) {

}

Step 1: identifica il carattere nella frase.

Per farlo, avremo bisogno di stabilire un alfabeto a cui fare riferimento.

Crea una variabile alphabet che contiene le 26 lettere dell'alfabeto.

String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
String alphabet2 = alphabet.toLowerCase();

Step 2: trova la posizione del carattere nell'alfabeto.

Poi crea un loop for che itera su ogni carattere del messaggio. Sarà più semplice svolgere quest'operazione se creiamo uno StringBuilder.

StringBuilder encrypted = new StringBuilder(message);
for (int q = 0; q < encrypted.length(); q++) {
    char currchar = encrypted.charAt(q);
    int index = alphabet.indexOf(currchar);
}

A questo punto, dovremmo assicurarci che la posizione corrisponda a una lettera.

if (index != -1) {}

Step 3:  identifica la somma di posizione del carattere + posizione della chiave nell'alfabeto.

Se è una lettera, allora dobbiamo trovare la posizione nell'alfabeto modificato, Non abbiamo ancora creato una variabile per l'alfabeto modificato, quindi dovremmo farlo adesso.

Step 4: costruisci una nuova frase usando i nuovi caratteri al posto di quelli originali.

Una volta trovato il valore nell'alfabeto modificato, dovremmo impostarlo sulla stessa posizione nello StringBuilder che abbiamo creato.

public String Encryption(String input, int key) {
        StringBuilder encrypted = new StringBuilder(input);
        String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        String alphabet2 = alphabet.toLowerCase();
        String keyedalphabet = alphabet.substring(key) + alphabet.substring(0, key);
        for (int q = 0; q < encrypted.length(); q++) {
            char currChar = encrypted.charAt(q);
            int index = alphabet.indexOf(currChar);
            if (index != -1) {
                char newChar = keyedalphabet.charAt(index);
                encrypted.setCharAt(q, newChar);
            }

Step 5: ripeti fino a raggiungere la lunghezza della frase (loop for).

Ora, abbiamo controllato se il carattere è maiuscolo, ma dobbiamo controllare anche se è minuscolo. Per farlo, dobbiamo accedere a alphabet2 che abbiamo creato precedentemente.

index = alphabet2.indexOf(currChar);
if (index != -1) {
    String keyedalphabet2 = keyedalphabet.toLowerCase();
    char newChar = keyedalphabet2.charAt(index);
    encrypted.setCharAt(q, newChar);
}

Step 6: restituisci il risultato.

Una volta completato il loop for, tutto ciò che ci resta da fare è restituire la stringa.

public String Encryption(String input, int key) {
    StringBuilder encrypted = new StringBuilder(input);
    String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    String alphabet2 = alphabet.toLowerCase();
    String keyedalphabet = alphabet.substring(key) + alphabet.Asubstring(0, key);
    for (int q = 0; q < encrypted.length(); q++) {
        char currChar = encrypted.charAt(q);
        int index = alphabet.indexOf(currChar);
        if (index != -1) {
            char newChar = keyedalphabet.charAt(index);
            encrypted.setCharAt(q, newChar);
        }
        index = alphabet2.indexOf(currChar);
        if (index != -1) {
            String keyedalphabet2 = keyedalphabet.toLowerCase();
            char newChar = keyedalphabet2.charAt(index);
            encrypted.setCharAt(q, newChar);
        }
    }
    return encrypted
}

Step 7: Debug.

Un momento! Così non funzionerà! encrypted non è una stringa, ma uno StringBuilder e questa funzione richiede specificatamente che venga restituita una stringa.

Fortunatamente, esiste una funzione molto semplice per rimediare a  questa svista.

public String Encryption(String input, int key) {
    StringBuilder encrypted = new StringBuilder(input);
    String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    String alphabet2 = alphabet.toLowerCase();
    String keyedalphabet = alphabet.substring(key) + alphabet.substring(0, key);
    for (int q = 0; q < encrypted.length(); q++) {
        char currChar = encrypted.charAt(q);
        int index = alphabet.indexOf(currChar);
        if (index != -1) {
            char newChar = keyedalphabet.charAt(index);
            encrypted.setCharAt(q, newChar);
        }
        index = alphabet2.indexOf(currChar);
        if (index != -1) {
            String keyedalphabet2 = keyedalphabet.toLowerCase();
            char newChar = keyedalphabet2.charAt(index);
            encrypted.setCharAt(q, newChar);
        }
    }
    return encrypted.toString();
}

Ecco come puoi ottenere la versione codificata della tua frase originale. Prova tu stesso!

Grazie per aver letto quest'articolo.

Gli algoritmi di forza bruta (o ricerca esaustiva) sono esattamente ciò che il loro nome suggerisce: sono dei metodi diretti di risoluzione di problemi che si basano sulla pura potenza computazionale utilizzando ogni possibilità, piuttosto che tecniche avanzate mirate a migliorare l'efficienza.

Ad esempio, immagina di avere un lucchetto con una combinazione a 4 cifre, ognuna da 0 a 9. Hai dimenticato la combinazione, ma non vuoi comprarne uno nuovo. Visto che non ricordi nessuna cifra, devi usare un metodo di forza bruta per aprirlo.

Quindi riporti tutti i numeri su 0 e inizi a provare tutti le possibili combinazioni, una alla volta: 0001, 0002, 0003 e così via finché non si apre. Nel caso peggiore, ti serviranno 10⁴ (10,000) tentativi prima di trovare la combinazione corretta.

Nel campo informatico, un esempio classico è quello del problema del commesso viaggiatore. Supponiamo che un commesso abbia bisogno di recarsi in 10 città del Paese. Come si può determinare l'ordine in cui dovrà visitarle in modo da minimizzare la distanza totale percorsa?

La soluzione forza bruta si basa semplicemente sul calcolo della distanza di ogni possibile percorso per poi selezionare il più corto. Questo modo di operare non è particolarmente efficiente perché è possibile eliminare molti percorsi utilizzando degli algoritmi ingegnosi.

La complessità temporale di forza bruta è O(mn), talvolta riportata come O(n*m), quindi se cerchiamo una stringa di "n" caratteri in una stringa di "m" caratteri usando un metodo forza bruta, ci occorreranno n * m tentativi.

Più informazioni sugli algoritmi

In informatica, un algoritmo è semplicemente un insieme di procedure sistematiche per risolvere un determinato problema. Gli algoritmi possono essere progettati per effettuare calcoli, processare dati o compiere operazioni logiche automatizzate.

Ecco la definizione di algoritmo secondo Wikipedia:

Un algoritmo è un metodo efficace che può essere espresso in uno spazio e in un tempo finiti e in un ben definito linguaggio formale per calcolare una funzione. Partendo da uno step iniziale e un input iniziale (anche nullo), le istruzioni descrivono un calcolo che, quando eseguito, procede attraverso un numero finito di stati ben precisati, producendo infine un "output" e terminando in uno stato finale. La transizione tra uno stato al successivo non è necessariamente deterministica; alcuni algoritmi, noti come randomizzati, utilizzano input casuali.

Ci sono alcuni requisiti a cui un algoritmo deve attenersi. Un algoritmo deve essere:

1. Deterministico: ogni step del processo deve essere definito in modo preciso.
2. Calcolabile: ogni step del processo deve poter essere svolto da un computer.
3. Finito: alla fine, il programma deve terminare con successo.

Tra i tipi più comuni ci sono gli algoritmi di:

• Ordinamento
• Ricerca
• Compressione

Le classi degli algoritmi includono

• Grafi
• Programmazione dinamica
• Ordinamento
• Ricerca
• Stringhe
• Matematica
• Geometria computazionale
• Ottimizzazione
• Altro

Anche se tecnicamente non sono classi di algoritmi, le strutture di dati vengono spesso incluse nell'elenco.

Efficienza

Gli algoritmi vengono spesso valutati in base alla loro efficienza e alla quantità di risorse di calcolo di cui hanno bisogno per operare.

Un modo comune di valutare un algoritmo è considerare la sua complessità temporale, che riflette la crescita del tempo di esecuzione di un algoritmo all'aumentare della dimensione degli input. Dato che gli algoritmi al giorno d'oggi devono operare su dati di input consistenti, è essenziale che abbiano un tempo di esecuzione ragionevole.

Algoritmi di ordinamento

Gli algoritmi di ordinamento sono piuttosto variabili a seconda della necessità. Tra quelli più comuni ci sono:

Quicksort

Non c'è discussione sull'ordinamento che possa terminare senza l'algoritmo quicksort. Qui troverai i concetti di base.

Mergesort

È un algoritmo che si basa sul concetto usato per unire degli array in un unico array ordinato. Qui puoi approfondire questo argomento.

Il curriculum di freeCodeCamp dà molta importanza alla creazione di algoritmi. Questo perché l'utilizzo di algoritmi è un ottimo modo per fare pratica con la programmazione ed è un'abilità molto richiesta per un lavoro da sviluppatore.

Libri sugli algoritmi in JavaScript:

Data Structures in JavaScript

• Libro gratuito che parla di strutture di dati in JavaScript.
• GitBook

Learning JavaScript Data Structures and Algorithms - Second Edition

• Tratta di programmazione orientata agli oggetti, Covers object oriented programming, ereditarietà prototipale, algoritmi di ordinamento e ricerca, quicksort, mergesort, alberi di ricerca binaria e concetti avanzati degli algoritmi.
• Amazon
• ISBN-13: 978-1785285493

Data Structures and Algorithms with JavaScript: Bringing classic computing approaches to the Web

• Tratta di ricorsività, ordinamento e ricerca, Covers recursion, sorting and searching algorithms, liste concatenate e alberi di ricerca binaria.
• Amazon
• ISBN-13: 978-1449364939

La notazione O-grande è un modo di descrivere la velocità o la complessità di un dato algoritmo. Se il tuo progetto attuale richiede un algoritmo predefinito, è importante capire quanto questo sia veloce o lento rispetto ad altre opzioni.

Cos'è la notazione O-grande e come funziona?

La notazione O-grande esprime il numero di operazioni compiute da un algoritmo. Prende il nome dalla "O" maiuscola posta davanti al numero stimato di operazioni.

Quello che la notazione O-grande non ti dice è la velocità di un algoritmo in secondi. Ci sono troppi fattori che influenzano il tempo necessario all'esecuzione di un algoritmo. Invece, utilizzerai la notazione O-grande per confrontare algoritmi diversi tramite il numero di operazioni che svolgono.

La O-grande definisce il tempo di esecuzione per il caso peggiore

Immagina di essere un insegnante e di avere uno studente di nome Gianni. Vuoi trovare i suoi dati usando un algoritmo di ricerca semplice cercando nel database della tua scuola.

La ricerca semplice viene eseguita in O(n) volte. Ciò vuol dire che, nel caso peggiore, dovrai cercare tra tutti i singoli dati (rappresentati da n) per trovare quelli di Gianni.

Ma quando esegui la ricerca semplice, trovi che i dati di Gianni sono la prima voce del database. Non devi analizzare ogni voce perché hai trovato i dati che cercavi al primo tentativo.

Questo algoritmo impiega un tempo O(n)? Oppure O(1), visto che hai trovato i dati al primo colpo?

In questo caso, o(1) rappresenta il caso più favorevole - sei stato fortunato e hai trovato i dati di Gianni in cima al database. La notazione O-grande si riferisce al caso peggiore, che è o(n) per una ricerca semplice. La certezza è che la ricerca semplice non sarà mai più lunga di un tempo O(n).

I tempi di esecuzione degli algoritmi crescono a velocità diverse

Considera di impiegare 1 millisecondo per controllare ciascun elemento del database della scuola.

Con una ricerca semplice, se devi controllare 10 voci, impiegherai 10 ms, ma con un algoritmo di ricerca binaria devi controllare soltanto 3 elementi, impiegando 3 ms.

Nella maggior parte dei casi, la lista o il database in cui effettui la ricerca avranno centinaia o migliaia di elementi.

Se c'è 1 miliardo di elementi, usando la ricerca semplice il tempo massimo necessario è 1 miliardo di ms, o 11 giorni. D'altro canto, usando la ricerca binaria ci vorranno soltanto 32 ms nel caso più sfavorevole:

Chiaramente i tempi di esecuzione per una ricerca semplice e per una ricerca binaria non crescono alla stessa velocità. Man mano che le voce in elenco aumentano, la ricerca binaria impiega un po' più di tempo. Il tempo di esecuzione della ricerca semplice cresce esponenzialmente man mano che le voci in elenco aumentano.

Ecco perché è importante sapere come cresce il tempo di esecuzione in relazione alla dimensione di un elenco ed è esattamente ciò per cui la notazione O-grande risulta utile.

La notazione O-grande mostra il numero di operazioni

Come detto precedentemente, la notazione O-grande non mostra il tempo che un algoritmo impiega per essere eseguito, ma indica il numero di operazioni che svolge e quanto velocemente cresce in confronto ad altri.

Ecco alcuni algoritmi comuni con i relativi tempi di esecuzione in notazione O-grande:

Adesso ne sai abbastanza sulla notazione O-grande per iniziare a confrontare algoritmi!

Se hai sempre voluto conoscere e capire l'algoritmo di Dijkstra, questo è l'articolo che fa per te. Vedrai come funziona passo passo con delle spiegazioni grafiche.

In quest'articolo imparerai:

• Concetti di base dei grafi (un breve riassunto).
• Per cosa viene utilizzato l'algoritmo di Dijkstra.
• Come funziona in background con degli esempi.

Iniziamo! ✨

🔹 Introduzione ai grafi

Iniziamo con una breve introduzione sui grafi.

Concetti di base

I grafi sono strutture di dati usate per rappresentare "connessioni" tra coppie di elementi.

• Questi elementi vengono chiamati nodi e possono rappresentare oggetti della vita reale, persone o entità.
• Le connessioni tra i nodi sono chiamate archi.

Ecco una rappresentazione grafica di un grafo:

I nodi sono rappresentati con dei cerchi colorati e gli archi con delle linee che connettono i cerchi.

💡 Suggerimento: due nodi sono connessi se c'è un arco tra di loro.

Applicazioni

I grafi vengono utilizzati direttamente in situazioni reali. Ad esempio, possiamo usarli per progettare una rete di trasporto in cui i nodi rappresentano le strutture che inviano o ricevono dei prodotti e gli archi rappresentano le strade o i percorsi che le collegano (vedi qui sotto).

Tipi di grafi

I grafi possono essere:

• Non orientati: se per ogni coppia di nodi connessi, puoi andare da un nodo all'altro in entrambi i versi.
• Orientati: se per ogni coppia di nodi connessi, puoi muoverti da un nodo all'altro soltanto in una verso specifico. Utilizziamo delle frecce, invece di semplici linee, per rappresentare gli archi orientati.

💡 Suggerimento: in quest'articolo, avremo a che fare con grafi non orientati.

Grafi pesati

Un grafo pesato è un grafo ai cui archi è associato un "peso" o un "costo". Il peso di un arco può rappresentare una distanza, un tempo o qualsiasi altra cosa relativa alla connessione che l'arco stabilisce tra due nodi.

Ad esempio, nel grafo pesato qui sotto, puoi vedere un numero in blu, riportato vicino ad ogni arco. Questo numero viene usato per rappresentare il peso dell'arco corrispondente.

💡 Suggerimento: come vedrai tra poco, questi pesi sono essenziali per l'algoritmo di Dijkstra.

🔸 Introduzione all'algoritmo di Dijkstra

Adesso che conosci i concetti di base dei grafi, possiamo iniziare a parlare di questo meraviglioso algoritmo.

• Scopo e casi di utilizzo
• Storia
• Concetti di base dell'algoritmo di Dijkstra
• Requisiti

Scopo e casi di utilizzo

Con l'algoritmo di Dijkstra, puoi trovare il cammino minimo che intercorre tra i nodi di un grafo. In particolare, puoi trovare il cammino minimo tra un nodo (chiamato "nodo sorgente") e tutti gli altri nodi del grafo, producendo un albero dei cammini minimi.

Questo algoritmo viene usato nei dispositivi GPS per cercare il cammino minimo tra la località attuale e quella di destinazione e ha ampie applicazione nell'industria, specialmente in campi che richiedono la modellazione di network.

Storia

Questo algoritmo è stato creato e pubblicato da Dr. Edsger W. Dijkstra, un brillante informatico olandese e ingegnere del software.

Nel 1959, ha pubblicato un articolo di 3 pagine intitolato "A note on two problems in connexion with graphs" in cui ha illustrato il suo nuovo algoritmo.

Durante un'intervista nel 2001, il Dr. Dijkstra ha rivelato come e perché ha sviluppato l'algortitmo:

Come ottenere il percorso più breve per viaggiare da Rotterdam a Groningen? Con l'algoritmo per il cammino minimo che ho creato in circa 20 minuti. Una mattina, mi trovavo con la mia giovane fidanzata a fare shopping ad Amsterdam. Eravamo stanchi e ci siamo seduti sulla terrazza di un bar a bere un caffè, mentre stavo pensando a come risolvere questo problema e poi ho elaborato l'algoritmo per il cammino minimo. Come ho detto, è stata una invenzione da 20 minuti. Il lavoro fu pubblicato nel 1959, tre anni dopo. La pubblicazione è piuttosto bella e una  delle ragioni che la rende così bella è che ho progettato il tutto senza carta e penna. In questo modo, sei quasi forzato a evitare ogni inutile complessità. Alla fine quell'algoritmo è diventato, con mio grande stupore, una delle pietre angolari della mia fama. - Come citato nell'articolo Edsger W. Dijkstra da An interview with Edsger W. Dijkstra.

⭐ Incredibile, vero? In soli 20 minuti, il Dr. Dijkstra ha elaborato uno dei più famosi algoritmi nella storia dell'informatica.

Concetti di base dell'algoritmo di Dijkstra

• Sostanzialmente, l'algoritmo di Dijkstra parte dal nodo che scegli (il nodo sorgente) e analizza il grafo per trovare il percorso più breve tra quel nodo e tutti gli altri nodi del grafo.
• L'algoritmo tiene traccia delle attuali distanze più brevi tra ogni nodo e il nodo sorgente e aggiorna questi valori quando trova un percorso più breve.
• Una volta che l'algoritmo ha trovato il tragitto più breve tra il nodo sorgente e un altro nodo, quest'ultimo viene segnato come "visitato" a aggiunto al percorso.
• Il processo continua finché tutti i nodi nel grafo sono stati aggiunti al percorso. In questo modo, otteniamo un percorso che connette il nodo sorgente a tutti gli altri nodi seguendo il cammino più breve possibile per raggiungere ogni nodo.

Requisiti

L'algoritmo di Dijkstra funziona soltanto con grafi che hanno pesi positivi. Questo perché, durante il processo, i pesi degli archi vengono sommati per trovare il cammino minimo.

Se nel grafo è presente un peso negativo, l'algoritmo non funzionerà adeguatamente. Una volta che un nodo viene segnato come "visitato", il percorso attuale per quel nodo viene indicato come il più breve per raggiungerlo. Un peso negativo può alterare il processo se il peso totale viene ridotto dopo questo step.

🔹 Esempi dell'algoritmo di Dijkstra

Ora che ne sai di più su quest'algoritmo, vediamo come funziona dietro le quinte con un esempio passo passo.

Consideriamo il grafo:

L'algoritmo genererà il percorso più breve tra il nodo 0 e tutti gli altri nodi nel grafo.

💡 Suggerimento: in questo grafo, assumeremo che i pesi degli archi rappresentino le distanze tra due nodi.

Il percorso più breve sarà quello tra il nodo 0 e il nodo 1, dal nodo 0 al nodo 2, dal nodo 0 al nodo 3 e così via per ogni nodo del grafo.

Inizialmente, abbiamo la lista delle distanze riportata di seguito:

• La distanza tra il nodo sorgente e sé stesso è 0. In quest'esempio, il nodo sorgente sarà il nodo 0 ma possiamo scegliere qualsiasi nodo.
• La distanza dal nodo sorgente a tutti gli altri nodi non è ancora stata determinata, quindi utilizziamo il simbolo di infinito per rappresentare questa condizione iniziale.

Abbiamo anche la seguente lista, che tiene traccia dei nodi che non sono stati ancora visitati (i nodi che non sono ancora stati inclusi nel percorso):

💡 Suggerimento: ricorda che l'algoritmo è completato una volta che tutti i nodi sono stati aggiunti al percorso.

Dato che abbiamo deciso di partire dal nodo 0, possiamo segnare questo nodo come visitato. In modo equivalente, lo cancelliamo dalla lista dei nodi non visitati e aggiungiamo un contorno rosso al nodo corrispondente nel diagramma:

Adesso abbiamo bisogno di iniziare a verificare le distanze tra il nodo 0 e i nodi adiacenti. Come puoi vedere, si tratta dei nodi 1 e2 (vedi gli archi rossi):

💡 Suggerimento: questo non significa che stiamo aggiungendo immediatamente i due nodi adiacenti al percorso più breve. Prima di fare ciò, dobbiamo verificare se abbiamo trovato il percorso più breve per raggiungerli. Stiamo semplicemente svolgendo una valutazione iniziale per analizzare le opzioni disponibili.

Dobbiamo aggiornare le distanze dal nodo 0 al nodo 1 e al nodo 2 con i pesi degli archi che li connettono al nodo 0 (il nodo sorgente). Questi pesi sono rispettivamente 2 e 6:

Una volta aggiornate le distanze dei nodi adiacenti, abbiamo bisogno di:

• Selezionare il nodo più vicino al nodo sorgente in base alle distanze attuali conosciute.
• Segnarlo come visitato.
• Aggiungerlo al percorso.

Se controlliamo la lista delle distanze, possiamo vedere che al nodo 1 corrisponde la distanza minore dal nodo sorgente (distanza di 2), quindi lo aggiungiamo al percorso.

Nel diagramma, lo rappresentiamo con un arco rosso:

Lo segniamo con un quadrato rosso nella lista per indicare che è stato visitato e che abbiamo trovato il percorso più breve per questo nodo:

E lo cancelliamo dalla lista dei nodi non visitati:

Adesso dobbiamo analizzare i nuovi nodi adiacenti per trovare il percorso più breve per raggiungerli. Consideriamo soltanto i nodi adiacenti ai nodi che fanno già parte del percorso più breve (quello marcata dagli archi rossi).

I nodi 3 e 2 sono entrambi vicini ai nodi che fanno già parte del percorso perché, come puoi vedere qui sotto, sono direttamente collegati rispettivamente ai nodi 1 e 0. Questi sono i nodi che analizzeremo nel prossimo passaggio.

Dato che abbiamo già la distanza tra il nodo sorgente e il nodo 2 scritta nella nostra lista, stavolta non dobbiamo aggiornarla. Dobbiamo soltanto aggiornare la distanza tra il nodo sorgente e il nuovo nodo adiacente (nodo 3):

La distanza è 7. Vediamo perché.

Per trovare la distanza tra nodo sorgente e un altro nodo (in questo caso, il nodo 3), aggiungiamo i pesi di tutti gli archi che determinano il cammino minimo per raggiungere il nodo:

• Per il nodo 3: la distanza totale è 7 perché aggiungiamo i pesi degli archi che formano il percorso 0 -> 1 -> 3 (2  per l'arco 0 -> 1 e 5 per l'arco 1 -> 3).

Ora che conosciamo la distanza dei nodi adiacenti, dobbiamo scegliere quale nodo verrà aggiunto al percorso. Dobbiamo selezionare un nodo non visitato con la distanza minore (attualmente conosciuta) dal nodo sorgente.

Se diamo un'occhiata alla lista delle distanze, possiamo immediatamente renderci conto che è il nodo 2 alla distanza 6:

Lo aggiungiamo al percorso graficamente contrassegnandolo in rosso:

Segniamo il nodo come visitato aggiungendo un quadratino rosso nella lista delle distanze e cancellandolo dalla lista dei nodi non visitati:

Adesso abbiamo bisogno di ripetere il processo per trovare il percorso più breve dal nodo sorgente al nuovo nodo adiacente, ovvero il nodo 3.

Come puoi notare, ci sono due percorsi possibili: 0 -> 1 -> 3 o 0 -> 2 -> 3. Vediamo come stabilire quale dei due è il più corto.

La distanza del nodo 3 è già stata inserita nella lista (7, vedi la lista precedente). Questa distanza risultava da uno step precedente, in cui abbiamo aggiunto i pesi 5 e 2 degli archi da percorrere nel tragitto 0 -> 1 -> 3.

Adesso, abbiamo un'altra alternativa. Se scegliamo di seguire il percorso 0 -> 2 -> 3, avremo bisogno di passare per gli archi 0 -> 2 and 2 -> 3 che hanno rispettivamente peso 6 e 8, per una distanza totale di 14.

Chiaramente, la prima distanza è minore (7 vs 14), così sceglieremo il percorso originario 0 -> 1 -> 3. Aggiorniamo la distanza solo se il nuovo percorso è più corto.

Quindi, aggiungiamo questo nodo al percorso usando la prima alternativa: 0 -> 1 -> 3.

Segniamo il nodo come visitato e lo cancelliamo dalla lista dei nodi non visitati:

E ripetiamo di nuovo il processo.

Valutiamo i nodi adiacenti che non sono stati ancora visitati. Questa volta, si tratta dei nodi 4 e 5 dato che sono contigui al nodo 3.

Aggiorniamo le distanze di questi nodi dal nodo sorgente, cercando sempre il tragitto più corto:

• Per il nodo 4: la distanza è 17, seguendo il percorso  0 -> 1 -> 3 -> 4.
• Per il nodo 5: la distanza è 22 seguendo il percorso 0 -> 1 -> 3 -> 5.

💡 Suggerimento: nota che abbiamo considerato soltanto di estendere il percorso più breve (segnato in rosso). Non possiamo considerare di passare attraverso archi che non sono stati aggiunti al percorso più breve (ad esempio, non possiamo usare il percorso che contiene l'arco 2 -> 3).

Adesso, dobbiamo scegliere quale nodo non visitato verrà segnato come visitato. In questo caso, si tratta del nodo 4 perché ha la distanza minore nella lista delle distanze. Lo aggiungiamo graficamente al diagramma:

Inoltre, lo segniamo  come "visitato" aggiungendo un quadratino rosso nella lista:

E lo cancelliamo dalla lista dei nodi non visitati:

Ripetiamo ancora il processo. Valutiamo i nodi adiacenti: nodi 5 e 6. Dobbiamo analizzare ogni possibile percorso che possiamo seguire per raggiungerli partendo dai nodi già visitati e aggiunti al percorso.

Per il nodo 5:

• La prima opzione è di seguire il percorso 0 -> 1 -> 3 -> 5, che ha distanza 22 dal nodo sorgente (2 + 5 + 15). Questa distanza è già stata registrata nella lista delle distanze nello step precedente.
• La seconda opzione è di seguire il percorso 0 -> 1 -> 3 -> 4 -> 5, che ha distanza 23 dal nodo sorgente (2 + 5 + 10 + 6).

Ovviamente, il primo percorso è più corto e lo scegliamo per raggiungere il nodo 5.

Per il nodo 6:

• Il percorso disponibile è 0 -> 1 -> 3 -> 4 -> 6, che ha distanza 19 dal nodo sorgente (2 + 5 + 10 + 2).

Segniamo come visitato il nodo con la distanza (attualmente conosciuta) più breve. In questo caso, il nodo 6.

E lo cancelliamo dalla lista dei nodi non visitati:

Adesso, abbiamo questo percorso (segnato in rosso):

Soltanto il nodo 5 non è stato ancora visitato. Vediamo come includerlo nel percorso.

Ci sono tre diversi percorsi che possiamo usare per raggiungere il nodo 5 dai nodi che abbiamo aggiunto al percorso:

• Opzione 1: 0 -> 1 -> 3 -> 5 con una distanza di 22 (2 + 5 + 15).
• Opzione 2: 0 -> 1 -> 3 -> 4 -> 5 con una distanza di 23 (2 + 5 + 10 + 6).
• Opzione 3: 0 -> 1 -> 3 -> 4 -> 6 -> 5 con una distanza di 25 (2 + 5 + 10 + 2 + 6).

Selezioniamo il percorso più breve: 0 -> 1 -> 3 -> 5 con una distanza di 22.

Segniamo il nodo come visitato e lo cancelliamo dalla lista dei nodi non visitati:

E voilà! Abbiamo il risultato finale del percorso più breve dal nodo 0 ad ogni nodo del grafo.

Nel diagramma, il percorso più breve è segnato in rosso. Devi seguire questi archi per percorrere il cammino minimo che collega un dato nodo con quello sorgente (nodo 0).

Ad esempio, se vuoi raggiungere il nodo 6 partendo dal nodo 0, devi semplicemente seguire gli archi evidenziati in rosso e percorrerai automaticamente 0 -> 1 -> 3 -> 4 - > 6.

🔸 In conclusione

• I grafi vengono utilizzati per creare modelli di connessioni tra oggetti, persone o entità. Sono costituiti da due elementi principali: nodi e archi. I nodi rappresentano gli oggetti e gli archi rappresentano le connessioni tra essi.
• L'algoritmo di Dijkstra trova il cammino minimo tra un dato nodo (denominato "sorgente") e tutti gli altri nodi in un grafo.
• Questo algoritmo utilizza i pesi degli archi per trovare il percorso che minimizza la distanza totale tra il nodo sorgente e gli altri nodi.

Spero davvero che quest'articolo ti sia piaciuto e che ti abbia aiutato. Adesso sai come funziona l'algoritmo di Dijkstra.