Bubble Sort è un semplice algoritmo di ordinamento che scorre ripetutamente l'elenco, confronta gli elementi adiacenti e li scambia se sono nell'ordine sbagliato. Si chiama 'Bubble Sort' perché gli elementi più piccoli 'bollano' in cima all'elenco. Pur non essendo l'algoritmo di ordinamento più efficiente, è facile da comprendere e implementare, il che lo rende un buon punto di partenza per conoscere gli algoritmi di ordinamento. In questo articolo approfondiremo il concetto di Bubble Sort, forniremo un'implementazione Python con output e discuteremo la complessità temporale dell'algoritmo.

Comprendere l'ordinamento a bolle

L'idea di base alla base di Bubble Sort è quella di scorrere l'elenco più volte, confrontando gli elementi adiacenti e scambiandoli se non sono in ordine. Il processo continua finché non sono più necessari scambi, indicando che l'elenco è ora ordinato. L'algoritmo prende il nome dal modo in cui gli elementi più piccoli si spostano gradualmente in cima all'elenco, proprio come le bolle che salgono in superficie.

Analizziamo i passaggi dell'algoritmo Bubble Sort:

1. Scorri l'elenco: inizia dall'inizio dell'elenco e confronta ogni coppia di elementi adiacenti.
2. Confronta e scambia: se gli elementi sono nell'ordine sbagliato, scambiali. Ciò garantisce che l'elemento più grande 'ribollisca' e quello più piccolo si sposti verso il basso.
3. Continua l'iterazione: ripeti il ​​processo per ogni coppia di elementi adiacenti fino al raggiungimento della fine dell'elenco.
4. Ripeti fino all'ordinamento: continua a scorrere l'elenco finché non sono più necessari scambi. A questo punto la lista è ordinata.

Sebbene Bubble Sort sia semplice da comprendere, non è l'algoritmo di ordinamento più efficiente, soprattutto per set di dati di grandi dimensioni. La sua complessità temporale è O(n^2) nel caso peggiore, dove 'n' è il numero di elementi nell'elenco. Questa complessità temporale quadratica lo rende meno adatto a set di dati di grandi dimensioni rispetto ad algoritmi di ordinamento più avanzati.

Implementazione Python di Bubble Sort

Ora implementiamo Bubble Sort in Python e osserviamo il suo comportamento con un elenco di esempio:

 def bubble_sort(arr): n = len(arr) # Traverse through all array elements for i in range(n): # Last i elements are already sorted, so we don't need to check them for j in range(0, n-i-1): # Swap if the element found is greater than the next element if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # Example usage if __name__ == '__main__': # Sample list to be sorted sample_list = [64, 34, 25, 12, 22, 11, 90] # Display the original list print('Original List:', sample_list) # Apply Bubble Sort bubble_sort(sample_list) # Display the sorted list print('Sorted List:', sample_list) 

In questa implementazione, la funzione bubble_sort accetta una lista (arr) come parametro e la ordina sul posto. Il ciclo annidato confronta gli elementi adiacenti e li scambia se sono nell'ordine sbagliato. Il ciclo esterno garantisce che il processo venga ripetuto finché l'intero elenco non viene ordinato.

come eseguire uno script in Linux

Risultati e spiegazione

Eseguiamo il codice Python fornito con l'elenco di esempi e osserviamo l'output:

 Original List: [64, 34, 25, 12, 22, 11, 90] Sorted List: [11, 12, 22, 25, 34, 64, 90] 

Qui, l'elenco originale [64, 34, 25, 12, 22, 11, 90] viene ordinato con successo utilizzando l'algoritmo Bubble Sort, ottenendo l'elenco ordinato [11, 12, 22, 25, 34, 64, 90].

L'algoritmo scorre l'elenco più volte, confrontando e scambiando elementi fino a quando l'intero elenco non viene ordinato. In ogni passaggio, l'elemento non ordinato più grande 'ribolle' nella sua posizione corretta. Questo processo continua finché non sono più necessari scambi, indicando che l'elenco è completamente ordinato.

Anche se Bubble Sort ordina correttamente l'elenco, è importante notare che la sua complessità temporale lo rende meno efficiente per set di dati di grandi dimensioni rispetto ad altri algoritmi di ordinamento come Merge Sort o Quick Sort.

Complessità temporale del Bubble Sort

Comprendere la complessità temporale di un algoritmo è fondamentale per valutarne l’efficienza, soprattutto quando si ha a che fare con set di dati di grandi dimensioni. La complessità temporale di Bubble Sort è O(n^2) nel caso peggiore, dove 'n' è il numero di elementi nell'elenco.

Analizziamo l'analisi della complessità temporale:

• Il ciclo esterno viene eseguito per 'n' iterazioni, dove 'n' è il numero di elementi nell'elenco.
• Anche il ciclo interno viene eseguito per 'n' iterazioni nel caso peggiore. Tuttavia, man mano che l'algoritmo procede, il numero di iterazioni nel ciclo interno diminuisce, poiché l'elemento non ordinato più grande viene posizionato nella posizione corretta in ogni passaggio.
• Nel peggiore dei casi, il numero di confronti e scambi è proporzionale al quadrato del numero di elementi nell'elenco, risultando nella complessità temporale O(n^2). Ciò rende Bubble Sort inefficiente per set di dati di grandi dimensioni e nelle applicazioni del mondo reale sono spesso preferiti algoritmi di ordinamento più avanzati con complessità temporali migliori.

Conclusione

In questo articolo abbiamo esplorato il concetto di Bubble Sort, un semplice algoritmo di ordinamento che confronta e scambia ripetutamente elementi adiacenti fino a ordinare l'intero elenco. Abbiamo fornito un'implementazione Python di Bubble Sort, l'abbiamo eseguita con un elenco di esempi e analizzato l'output. Inoltre, abbiamo discusso la complessità temporale di Bubble Sort, evidenziandone la complessità temporale O(n^2) nel caso peggiore e le sue implicazioni in termini di efficienza.