Da appunti a quiz

Maximilian

Introduzione

Di recente ho seguito un corso su 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 parlare di programmazione annoiando il mio partner per il mese (probabilmente per l'anno), ho pensato di scrivere una serie di post con alcune delle cose che ho imparato. Questo è uno di quei post.

Che cos'è l'algoritmo Bubble Sort

L'algoritmo Bubble Sort viene tipicamente applicato dove si preferisce la semplicità all'efficienza. Ha una complessità temporale di O(n^2), che è meno 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 pensarlo con 2 puntatori, pointer1 e pointer2. Iniziamo impostando entrambi i puntatori al primo elemento della lista. Poi attraversiamo l'intera lista con pointer2 e scambiamo l'elemento nella posizione di pointer2 se l'elemento in posizione pointer2 + 1 ha valore maggiore. Continuiamo a ripetere questo processo fino a raggiungere la fine della lista. Quindi 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 l'obiettivo 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 ampiamente commentata in TypeScript:

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 si ricorre probabilmente nella maggior parte dei casi, ma penso che sia carino e semplice per iniziare. Spero che tu l'abbia trovato utile o, almeno, un po' interessante!