Ordinamento a bolle
Scorre la lista più volte e scambia i vicini che sono nell'ordine sbagliato. Dopo ogni passata, il valore più grande rimasto è in fondo.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- sì
- sì
Caso migliore: come cresce il tempo con la dimensione n della lista quando l'input è il più facile per questo algoritmo.
Caso medio: crescita tipica del tempo con n. Con n², raddoppiare il numero di valori quadruplica circa il tempo; n log n cresce molto meno.
Caso peggiore: la crescita sull'input più difficile. Utile quando la velocità non deve mai calare.
Spazio: quanta memoria extra serve oltre alla lista. 1 vuol dire poche variabili, n una copia della lista.
Stabile: due valori uguali mantengono il loro ordine originale. Conta quando si ordinano record in base a un solo campo.
Sul posto: ordina dentro la lista stessa, senza una seconda lista.
- confronto
- spostamento
- al suo posto finale
Coppie fuori ordine: 154 (all'inizio: 154) fuori ordine rimessa in ordine Entrambi gli assi: valori dal più piccolo al più grande
Premi Riproduci: le linee mostrano come cresce il costo
Premi Riproduci o avanza passo passo.
Spazio: riproduci o metti in pausa. Frecce sinistra e destra: passo passo. Home e Fine: salta.
Prova così: Scegli una lista quasi ordinata. Dopo una passata senza scambi, l'algoritmo si ferma prima.
Come funziona
Confronta due vicini alla volta e li scambia se quello a sinistra è più grande. Così a ogni passata il valore più grande arriva fino in fondo a destra, come una bolla che sale. Se una passata non fa nessuno scambio, la lista è già ordinata.
Quando conviene usarlo
Quasi mai nei programmi reali, perché è lento sulle liste lunghe. Per imparare è ottimo: mostra l'idea base dell'ordinamento, cioè confrontare e scambiare. È veloce solo se la lista è già ordinata.