Bubble sort
Bubble sort è un esperimento interattivo di Algoritmi in azione, una simulazione gratuita di StudyFi Lab che funziona direttamente nel browser.
Il bubble sort confronta elementi vicini e li scambia se sono nell’ordine sbagliato. Dopo ogni passata l’elemento più grande è “risalito” fino in fondo, quindi la parte non ordinata si accorcia. Se una passata non fa scambi, l’array è ordinato. Nel caso peggiore servono n(n−1)/2 confronti, cioè O(n²).
Prova questo: Scegli l’input invertito e confronta i confronti con n(n−1)/2. Poi prova un array quasi ordinato: finisce dopo poche passate.
Domande frequenti
Che cosa mostra l’esperimento «Bubble sort»?
Il bubble sort confronta elementi vicini e li scambia se sono nell’ordine sbagliato. Dopo ogni passata l’elemento più grande è “risalito” fino in fondo, quindi la parte non ordinata si accorcia. Se una passata non fa scambi, l’array è ordinato. Nel caso peggiore servono n(n−1)/2 confronti, cioè O(n²).
Come provo «Bubble sort»?
Scegli l’input invertito e confronta i confronti con n(n−1)/2. Poi prova un array quasi ordinato: finisce dopo poche passate.
Studi per una verifica?
Carica i tuoi appunti e StudyFi li trasforma in flashcard, test e podcast.