Bubble Sort è un semplice algoritmo utilizzato per ordinare un determinato insieme di n elementi forniti sotto forma di array con n numero di elementi. Bubble Sort confronta tutti gli elementi uno per uno e li ordina in base ai loro valori.
Se l’array dato deve essere ordinato in ordine crescente, il bubble sort inizierà confrontando il primo elemento dell’array con il secondo elemento, se il primo elemento è maggiore del secondo elemento, scambierà entrambi gli elementi, quindi passerà al confronto del secondo e del terzo elemento e così via.
Se abbiamo il totale n, quindi dobbiamo ripetere questo processo per n-1 volte.
È noto come Bubble sort, perché ad ogni iterazione completa l’elemento più grande nella matrice data, bolle verso l’alto verso l’ultimo punto o l’indice più alto, proprio come una bolla d’acqua sale fino alla superficie dell’acqua.
L’ordinamento avviene scorrendo tutti gli elementi uno per uno e confrontandolo con l’elemento adiacente e scambiandoli se necessario.
NOTA: Se non hai familiarità con l’ordinamento nella struttura dei dati, dovresti fi per prima cosa impara cosa significa l’ordinamento per sapere le basi dell’ordinamento.
Implementazione dell’algoritmo di ordinamento a bolle
Di seguito sono riportati i passaggi coinvolti nell’ordinamento a bolle (per ordinare un dato array in ordine crescente):
- A partire dal primo elemento (index = 0), confronta l’elemento corrente con l’elemento successivo dell’array.
- Se l’elemento corrente è maggiore dell’elemento successivo dell’array, scambiali.
- Se l’elemento corrente è minore dell’elemento successivo, passa all’elemento successivo. Ripeti il passaggio 1.
Consideriamo un array con valori {5, 1, 6, 2, 4, 3}
Di seguito, abbiamo un rappresentazione pittorica di come il Bubble sort ordinerà l’array dato.
Così come possiamo vedere nella rappresentazione sopra, dopo il prima iterazione, 6 viene posizionato nell’ultimo indice, che è la posizione corretta per esso.
Allo stesso modo dopo la seconda iterazione, 5 sarà al penultimo indice e così via.
È ora di scrivere il codice per il bubble sort:
Sebbene la logica di cui sopra ordinerà un array non ordinato, l’algoritmo di cui sopra non è efficiente perché secondo la logica di cui sopra, il for loop continuerà a essere eseguito per 6 iterazioni anche se l’array viene ordinato dopo la seconda iterazione.
Quindi, possiamo chiaramente ottimizzare il nostro algoritmo.
Algoritmo di ordinamento delle bolle ottimizzato
Per ottimizzare il nostro bubb le algoritmo di ordinamento, possiamo introdurre un flag per monitorare se gli elementi vengono scambiati all’interno del for loop.
Quindi, nel ciclo for interno, controlliamo se lo scambio di elementi sta avvenendo o meno, ogni volta.
Se per una particolare iterazione, nessuno scambio ha preso place, significa che l’array è stato ordinato e possiamo saltare fuori dal ciclo for, invece di eseguire tutte le iterazioni.
Consideriamo un array con i valori {11, 17, 18, 26, 23}
Di seguito, abbiamo una rappresentazione grafica di come l’ordinamento a bolle ottimizzato ordinerà l’array dato.
Come possiamo vedere, nella prima iterazione si è verificato lo scambio, quindi abbiamo aggiornato il nostro valore flag a 1, di conseguenza, l’esecuzione entra di nuovo nel ciclo for. Ma nella seconda iterazione, non si verificherà alcuno scambio, quindi il valore di flag rimarrà 0 e l’esecuzione verrà interrotta dal ciclo.
Nel codice precedente, nella funzione bubbleSort, se per un ciclo completo singolo di j iterazione (ciclo for interno), nessuno scambio, quindi flag rimarrà 0 e quindi usciremo dai cicli for, perché l’array è già stato ordinato.
Analisi della complessità di Bubble Sort
In Bubble Sort, n-1 i confronti verranno eseguiti nel primo passaggio, n-2 nel 2 ° passaggio, n-3 nel 3 ° passaggio e così via. Quindi il numero totale di confronti sarà,
(n-1) + (n-2) + (n-3) + ….. + 3 + 2 + 1 Somma = n (n- 1) /2i.e O (n2)
Quindi la complessità temporale di Bubble Sort è O (n2).
Il vantaggio principale di Bubble Sort è la semplicità dell’algoritmo.
La complessità dello spazio per Bubble Sort è O (1), perché è richiesto solo un singolo spazio di memoria aggiuntivo, ad esempio per la variabile temp.
Inoltre, la complessità temporale nel caso migliore sarà O (n), quando l’elenco è già ordinato.
Di seguito sono riportate le complessità Time e Space per l’algoritmo Bubble Sort.
Ora che abbiamo imparato l’algoritmo di ordinamento a bolle, puoi controllare questi algoritmi di ordinamento e anche le loro applicazioni:
- Ordinamento di inserzione
- Ordinamento di selezione
- Ordinamento rapido
- Unisci ordinamento
- Ordinamento heap
- Ordinamento conteggio
