Confronti
Scambi
Passata

  • Confrontate
  • Scambiate
  • Al loro posto

Scopri di più sul bubble sort

Bubble sort

Il bubble sort percorre una lista più e più volte, confronta ogni coppia di vicini e li scambia quando quello a sinistra è più grande. Dopo ogni passata, il valore più grande ancora fuori posto è salito fino in fondo. Avvia l'ordinamento a qualsiasi velocità, o procedi un confronto alla volta, e guarda i contatori di confronti, scambi e passate. Premi Avvia per guardare l'ordinamento, oppure Passo e Indietro per procedere un confronto alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto. I riquadri contano confronti, scambi e passate. Scegli quante barre usare, come partono, oppure inserisci i tuoi numeri. Con l'area selezionata, i tasti freccia avanzano di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.

Come funziona

  1. Scegli quante barre usare e come partono: casuali, quasi ordinate, in ordine inverso o con pochi valori distinti. Oppure inserisci i tuoi numeri.
  2. Premi Avvia, oppure usa Passo e Indietro per procedere un confronto alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto dell'ordinamento.
  3. Guarda i riquadri che contano confronti, scambi e passate, e confrontali con il caso peggiore.

Come funziona il bubble sort

Parti da sinistra. Confronta i primi due valori; se quello a sinistra è più grande, scambiali. Spostati di un posto a destra e confronta di nuovo, fino alla fine della lista. Questa è una passata, e lascia il valore più grande all'ultimo posto. La passata successiva si ferma un posto prima. Continua finché una passata non fa scambi, o finché resta un solo valore.

Contare il lavoro

Con n valori, la prima passata fa n − 1 confronti, la successiva n − 2 e così via, quindi un ordinamento completo fa al massimo n(n − 1)/2 confronti. Il numero di scambi è sempre il numero di inversioni nella lista iniziale: le coppie di valori nell'ordine sbagliato. Una lista inversa ne ha di più, n(n − 1)/2. Una lista ordinata non ne ha, e con l'arresto anticipato richiede una sola passata di n − 1 confronti.

Domande frequenti

Perché si chiama bubble sort?

Perché i valori grandi salgono verso la fine della lista come bolle (in inglese “bubble”) nell'acqua. In ogni passata, il valore più grande non ancora al suo posto si sposta passo dopo passo verso destra fino al suo posto definitivo.

Quanti confronti e scambi fa il bubble sort?

Al massimo n(n − 1)/2 confronti per n valori: 45 per 10 valori, 780 per 40. Gli scambi sono sempre pari al numero di inversioni nella lista iniziale, da zero per una lista ordinata a n(n − 1)/2 per una inversa.

A cosa serve l'arresto anticipato?

Se un'intera passata non fa scambi, ogni coppia di vicini è in ordine, quindi la lista è ordinata e l'ordinamento può fermarsi. Con l'arresto anticipato attivo, una lista ordinata richiede una passata. Senza, il bubble sort fa sempre tutte le n − 1 passate.

Il bubble sort si usa nella pratica?

Raramente. È semplice e stabile, ma in media richiede un tempo proporzionale a n². L'insertion sort fa lo stesso lavoro con meno passi su liste piccole o quasi ordinate, e il merge sort o il quicksort sono molto più veloci su quelle grandi.

I miei numeri vengono inviati da qualche parte?

No. L'ordinamento avviene nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Vai all'editor