Cos'è l'algoritmo Bubble Sort [spiegato con esempi]

L'ordinamento a bolle è uno degli algoritmi di ordinamento più semplici che scorre l'array specificato e confronta gli elementi adiacenti. Se gli elementi sono nell'ordine sbagliato, vengono scambiati per riportarli nell'ordine corretto. Questo processo continua finché l'intero array non viene ordinato.

Algoritmo:

Passaggio 1:esegui l'iterazione sull'array più volte

In ogni iterazione, confronta gli elementi adiacenti (i e i + 1)

Passaggio 2:se l'elemento corrente (i) è maggiore dell'elemento successivo (i + 1), scambiali

Ripeti questo processo finché l'intero array non viene ordinato

Complessità temporale:

O(n^2), poiché scorre l'array più volte ed esegue confronti e scambi in ogni iterazione.

Esempio di codice in Python:

def bolla_sort(arr):

for i in range(len(arr) - 1):

# Scorrere l'array per confrontare elementi adiacenti

for j in range(len(arr) - 1 - i):

# Confronta l'elemento corrente con l'elemento successivo

se arr[j]> arr[j + 1]:

# Scambia gli elementi se sono nell'ordine sbagliato

arr[j], arr[j + 1] =arr[j + 1], arr[j]

# Restituisce l'array ordinato

ritorno arr

Esempio:

Ingresso:

[5, 3, 1, 2, 4]

Produzione:

[1, 2, 3, 4, 5]

L'algoritmo di ordinamento delle bolle scorre l'array e confronta gli elementi adiacenti. Se sono nell'ordine sbagliato, vengono scambiati. Questo processo viene ripetuto finché l'intero array non viene ordinato.

Ecco come funziona l'algoritmo in questo esempio:

Iterazione 1:

- Confronta 5 e 3:scambiali poiché 5 è maggiore di 3.

- Confronta 3 e 1:scambiali poiché 3 è maggiore di 1.

- Confronta 2 e 4:non è necessario scambiarli poiché sono nell'ordine corretto.

- L'array diventa:[3, 1, 2, 4, 5].

Iterazione 2:

- Confronta 3 e 1:scambiali poiché 3 è maggiore di 1.

- Confronta 1 e 2:non è necessario scambiarli poiché sono nell'ordine corretto.

- Confronta 2 e 4:non è necessario scambiarli poiché sono nell'ordine corretto.

- L'array diventa:[1, 2, 3, 4, 5].

Iterazione 3:

- Confronta 1 e 2:non è necessario scambiarli poiché sono nell'ordine corretto.

- Confronta 2 e 3:non è necessario scambiarli poiché sono nell'ordine corretto.

- Confronta 3 e 4:non è necessario scambiarli poiché sono nell'ordine corretto.

- L'array diventa:[1, 2, 3, 4, 5].

Iterazione 4:

- Confronta 1 e 2:non è necessario scambiarli poiché sono nell'ordine corretto.

- Confronta 2 e 3:non è necessario scambiarli poiché sono nell'ordine corretto.

- Confronta 3 e 4:non è necessario scambiarli poiché sono nell'ordine corretto.

- L'array rimane invariato.

Dopo la quarta iterazione, l'array viene ordinato in ordine crescente:[1, 2, 3, 4, 5].

• Cos'è l'algoritmo di ordinamento rapido [spiegato con esempi] 
• Cos'è l'algoritmo di ordinamento della selezione [spiegato con un esempio pratico]