Bubble Sort è considerato uno degli algoritmi di ordinamento più semplici che funziona scambiando ripetutamente gli elementi adiacenti se sono nell’ordine sbagliato. Con un algoritmo di ordinamento a bolle sarai in grado di vedere che l’elemento più grande (supponendo che stiamo ordinando dal più piccolo al più grande) “bolla” fino all’inizio dell’elenco o dell’array.

Esempio:
Supponiamo di voler ordinare una lista o un array di elementi in ordine crescente (dal più piccolo al più grande): List = (3,1,2)

Poiché non si è verificato alcuno scambio, questo ci dice che l’array è già ordinato in ordine crescente!

Caso migliore

Ora proviamo di nuovo lo stesso algoritmo ma questa volta utilizzando lo scenario migliore, ovvero quando gli elementi sono già ordinati nell’ordine ( crescente) vorremmo.

Dato che non si è verificato alcuno scambio, l’algoritmo ha fatto solo 2 confronti e il numero di elementi nell’array lo chiameremo n = 3. Quindi possiamo vedere che per n elementi questo algoritmo nel migliore dei casi richiederà solo confronti n-1, n-1 = O (n)

La procedura o l’algoritmo che abbiamo usato è di seguito:

Questo algoritmo usa un flag per sapere se gli elementi sono stati scambiati o meno , che consente all’algoritmo di bubble sort nel migliore dei casi di essere O (n) invece di O (n²) come un’altra implementazione del bubble sort.

L’algoritmo precedente
Worst Case = O (n²)
Best Case = O (n)

Diamo un’occhiata a un’implementazione diversa dell’algoritmo di ordinamento delle bolle:

BUBBLESORT(A)
1 for i = 1 to A.length - 1
2 for j = A.length downto i + 1
3 if A < A
4 exchange A with A

L’algoritmo precedente
Caso peggiore = O (n²)
Caso migliore = O (n²)

Caso peggiore

Ordiniamo un array o una lista = (3,2,1) questo sarebbe il caso peggiore in cui l’elenco è nell’ordine completamente opposto a quello che desideriamo (in ordine crescente) usando l’algoritmo di cui sopra.

Primo passaggio:
(3,2,1) – > Confronta gli elementi 3 & 2
(2,3 , 1) – > Scambia 3 & 2 da 2 < 3
( 2,3,1) – > Confronta gli elementi 3 & 1
(2,1,3) – > Scambia 1 & 3 da 1 < 3

Secondo passaggio:
(2,1,3) – > Confronta gli elementi 2 & 1
(1,2,3) – > Scambia 2 & 1 da 1 < 2
(1,2,3) – > Confronta il elementi 2 & 3
(1,2,3) – > Nessuno SWAPPING necessario dal 2 < 3

Ora abbiamo terminato il ciclo attraverso entrambi i cicli, quindi l’array deve essere ordinato in ordine crescente.

Si noti che abbiamo fatto 4 confronti nel secondo esempio sopra e il numero di elementi nell’array che chiameremo ‘n’ = 3, quindi il numero di confronti effettuati è (n-1) ² e (n-1) ² = O (n²)

Anche un ottimo libro per prepararti alla programmazione / programmazione delle interviste si chiama cracking the coding interview. Ti aiuterà a familiarizzare con gli algoritmi di ordinamento e la risoluzione dei problemi, quindi assicurati di controllarlo!

Grazie per aver letto questo articolo, spero sia utile a tutti voi! Continua a imparare e se desideri altri video di analisi degli algoritmi, visita e iscriviti ai miei canali YouTube (randerson112358 & compsci112358)

Dai un’occhiata a quanto segue per altri contenuti / video sull’analisi e la programmazione degli algoritmi:

Canale YouTube:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:

Sito web:

Esercitazioni video sulla relazione di ricorrenza:

Esercitazione video sull’analisi degli algoritmi:

Twitter: