Algoritmi di ordinamento -> Bubble sort
Il Bubble sort è un algoritmo di ordinamento che opera in-place (o in loco, cioè l'ordinamento viene operato direttamente sull'array in input). Presenta una complessità variabile a seconda della lista presentata in input; nel caso migliore, ossia nel caso in cui la lista presentata in input sia già ordinata, presenta una complessità lineare pari a O(n), ma nel caso medio e peggiore presenta una complessità pari a O(n[SUP]2[/SUP]) e ciò lo rende abbastanza inefficiente in caso di n elevato.
L'algoritmo procede confrontando ciascun elemento con l'elemento che lo segue; se l'elemento è maggiore del suo successivo allora questi vengono scambiati di posizione. L'effetto è che gli elementi più grandi "levitano" verso l'alto (come bolle, da cui prende il nome l'algoritmo). Per avere un ordinamento questa procedura di confronti viene ripetuta n volte (dove n è la dimensione della lista).
Codice
Ottimizzazioni
Si possono effettuare alcune piccole ottimizzazioni su questo algoritmo e ora ne vediamo in breve due possibili che possiamo andare ad utilizzare per migliorare l'efficienza dell'algoritmo usato in partenza.
1. Ad una data iterazione i è possibile fermare i confronti alla posizione n-i. Infatti i primi i elementi maggiori saranno già in posizione ordinati nella parte finale della lista (vedi figura)
In rosso gli elementi oggetti di confronto, in nero gli elementi già in ordine all'iterazione i
Possiamo quindi andare a modificare il codice di partenza per tenere conto di questa osservazione; tutto ciò si traduce nella modifica della condizione del for nidificato ( j < n-i-1 )
2. Se ad una data iterazione i non viene effettuato nessuno scambio, allora la lista è già ordinata e si può interrompere l'algoritmo. Realizziamo questo comportamento mediante una variabile booleana che tiene traccia del fatto che vengano effettuati scambi o meno.
Il codice finale diventa quindi
Il Bubble sort è un algoritmo di ordinamento che opera in-place (o in loco, cioè l'ordinamento viene operato direttamente sull'array in input). Presenta una complessità variabile a seconda della lista presentata in input; nel caso migliore, ossia nel caso in cui la lista presentata in input sia già ordinata, presenta una complessità lineare pari a O(n), ma nel caso medio e peggiore presenta una complessità pari a O(n[SUP]2[/SUP]) e ciò lo rende abbastanza inefficiente in caso di n elevato.
L'algoritmo procede confrontando ciascun elemento con l'elemento che lo segue; se l'elemento è maggiore del suo successivo allora questi vengono scambiati di posizione. L'effetto è che gli elementi più grandi "levitano" verso l'alto (come bolle, da cui prende il nome l'algoritmo). Per avere un ordinamento questa procedura di confronti viene ripetuta n volte (dove n è la dimensione della lista).
Codice
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Ottimizzazioni
Si possono effettuare alcune piccole ottimizzazioni su questo algoritmo e ora ne vediamo in breve due possibili che possiamo andare ad utilizzare per migliorare l'efficienza dell'algoritmo usato in partenza.
1. Ad una data iterazione i è possibile fermare i confronti alla posizione n-i. Infatti i primi i elementi maggiori saranno già in posizione ordinati nella parte finale della lista (vedi figura)
In rosso gli elementi oggetti di confronto, in nero gli elementi già in ordine all'iterazione i
Possiamo quindi andare a modificare il codice di partenza per tenere conto di questa osservazione; tutto ciò si traduce nella modifica della condizione del for nidificato ( j < n-i-1 )
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
2. Se ad una data iterazione i non viene effettuato nessuno scambio, allora la lista è già ordinata e si può interrompere l'algoritmo. Realizziamo questo comportamento mediante una variabile booleana che tiene traccia del fatto che vengano effettuati scambi o meno.
Il codice finale diventa quindi
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Ultima modifica:
