Articolo originale
L'algoritmo Bubble Sort - DEV Community
Maximilian
Introduzione
Di recente ho seguito un corso di strutture dati e algoritmi come parte del mio percorso per apprendere concetti di programmazione di livello più basso e di informatica. Come dice il proverbio, il modo migliore per consolidare le proprie conoscenze su qualcosa è insegnarlo, e dato che ho già esaurito la mia quota di discorsi sulla programmazione che annoiano il mio partner per il mese (probabilmente per l'anno), ho pensato di scrivere una serie di post su alcune delle cose che ho imparato. Questo è uno di quei post.
Che cos'è l'algoritmo Bubble Sort
L'algoritmo Bubble Sort viene in genere applicato dove la semplicità è preferita all'efficienza. Ha una complessità temporale di O(n^2), che è meno che ideale quando si gestiscono liste più grandi.
Come funziona
Per spiegare come funziona, ecco dello pseudo-codice:
for pointer1 in list
for pointer2 in list
if list[j] > list[j + 1]
swap list[j] and list[j + 1]
pointer2++
pointer1++
L'idea di questo algoritmo è di 'far risalire' (bubble up) gli elementi più grandi della lista verso la fine. Possiamo pensarci con 2 puntatori, pointer1 e pointer2. Iniziamo impostando entrambi i puntatori sul primo elemento della lista. Poi attraversiamo l'intera lista con pointer2 e scambiamo l'elemento nella posizione di pointer2 se l'elemento nella posizione pointer2 + 1 ha valore maggiore. Continuiamo a ripetere questo processo finché non raggiungiamo la fine della lista. Poi spostiamo pointer1 avanti di 1 e ricominciamo il processo con pointer2.
Potresti aver notato che abbiamo bisogno di un modo per evitare di controllare elementi che abbiamo già ordinato. Dato che lo scopo di ogni iterazione è spostare gli elementi più grandi alla fine della lista, possiamo farlo limitando il confine di pointer2 al valore di pointer1 + 1.
Come lo implementiamo
Ecco un'implementazione in TypeScript con molti commenti:
function bubbleSort(arr: number[]): void {
// pointer 1
for (let i = 0; i < arr.length; ++i) {
// pointer 2 + limit iterations by pointer1 + 1
for (let j = 0; j < arr.length - 1 - i; ++j) {
// check if current item is larger than the next item
if (arr[j] > arr[j + 1]) {
// temporarily store the current item so we don't lose it
const tmp = arr[j];
// swap the items in the array
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
Ordinato
Non è un algoritmo a cui ricorrere di solito nella maggior parte dei casi, ma penso che sia un buon algoritmo semplice con cui iniziare. Spero che tu l'abbia trovato utile o, almeno, un po' interessante!