Cos'è un Bubble Sort?
Bubble Sort è un algoritmo di ordinamento utilizzato per ordinare gli elementi dell'elenco in ordine crescente confrontando due valori adiacenti. Se il primo valore è maggiore del secondo valore, il primo valore assume la posizione del secondo valore, mentre il secondo valore assume la posizione del primo valore. Se il primo valore è inferiore al secondo, non viene eseguito alcuno scambio.
Questo processo viene ripetuto finché tutti i valori in un elenco non sono stati confrontati e, se necessario, scambiati. Ogni iterazione viene solitamente chiamata passaggio. Il numero di passaggi in un Bubble sort è uguale al numero di elementi in un elenco meno uno.
In questo tutorial Bubble Sorting in Python imparerai:
- Cos'è un Bubble Sort?
- Implementazione dell'algoritmo Bubble Sort
- Algoritmo di ordinamento delle bolle ottimizzato
- Rappresentazione visiva
- Esempi di Python
- Spiegazione del codice
- Vantaggi del Bubble sort
- Bubble sort Svantaggi
- Analisi della complessità del Bubble Sort
Implementazione dell'algoritmo Bubble Sort
Suddivideremo l'implementazione in tre (3) passaggi, vale a dire il problema, la soluzione e l'algoritmo che possiamo utilizzare per scrivere codice per qualsiasi linguaggio.
Il problema
Viene fornito un elenco di articoli in ordine casuale e vorremmo disporre gli articoli in modo ordinato
Considera il seguente elenco:
[21,6,9,33,3]
La soluzione
Scorri l'elenco confrontando due elementi adiacenti e scambiandoli se il primo valore è maggiore del secondo.
Il risultato dovrebbe essere il seguente:
[3,6,9,21,33]
Algoritmo
L'algoritmo di Bubble Sort funziona come segue
Passaggio 1) Ottieni il numero totale di elementi. Ottieni il numero totale di elementi nell'elenco fornito
Passaggio 2) Determinare il numero di passate esterne (n - 1) da eseguire. La sua lunghezza è la lista meno uno
Passaggio 3) Eseguire passaggi interni (n - 1) volte per passaggio esterno 1. Ottenere il valore del primo elemento e confrontarlo con il secondo valore. Se il secondo valore è inferiore al primo valore, scambia le posizioni
Passaggio 4) Ripetere il passaggio 3 fino a raggiungere il passaggio esterno (n - 1). Ottieni l'elemento successivo nell'elenco, quindi ripeti il processo eseguito nel passaggio 3 finché tutti i valori non sono stati inseriti nel loro corretto ordine crescente.
Passaggio 5) Restituire il risultato quando tutti i passaggi sono stati eseguiti. Restituisce i risultati dell'elenco ordinato
Passaggio 6) Ottimizza l'algoritmo
Evita passaggi interni non necessari se l'elenco o i valori adiacenti sono già ordinati. Ad esempio, se l'elenco fornito contiene già elementi che sono stati ordinati in ordine crescente, è possibile interrompere il ciclo in anticipo.
Algoritmo di ordinamento delle bolle ottimizzato
Per impostazione predefinita, l'algoritmo per l'ordinamento a bolle in Python confronta tutti gli elementi nell'elenco indipendentemente dal fatto che l'elenco sia già ordinato o meno. Se l'elenco fornito è già ordinato, confrontare tutti i valori è una perdita di tempo e risorse.
L'ottimizzazione del Bubble Sort ci aiuta a evitare iterazioni non necessarie e a risparmiare tempo e risorse.
Ad esempio, se il primo e il secondo elemento sono già ordinati, non è necessario scorrere il resto dei valori. L'iterazione viene terminata e quella successiva viene avviata fino al completamento del processo, come mostrato nell'esempio di Bubble Sort di seguito.
L'ottimizzazione viene eseguita utilizzando i seguenti passaggi
Passaggio 1) Creare una variabile flag che monitora se si è verificato uno scambio nel ciclo interno
Passaggio 2) Se i valori hanno posizioni invertite, continuare con l'iterazione successiva
Passaggio 3) Se i vantaggi non si sono scambiati di posizione, terminare il ciclo interno e continuare con il ciclo esterno.
Un Bubble sort ottimizzato è più efficiente in quanto esegue solo i passaggi necessari e ignora quelli non richiesti.
Rappresentazione visiva
Dato un elenco di cinque elementi, le immagini seguenti illustrano come l'ordinamento a bolle esegue l'iterazione dei valori durante l'ordinamento
L'immagine seguente mostra l'elenco non ordinato
Prima iterazione
Passo 1)
I valori 21 e 6 vengono confrontati per verificare quale sia maggiore dell'altro.
21 è maggiore di 6, quindi 21 prende la posizione occupata da 6 mentre 6 prende la posizione che era occupata da 21
Il nostro elenco modificato ora assomiglia a quello sopra.
Passo 2)
I valori 21 e 9 vengono confrontati.
21 è maggiore di 9, quindi scambiamo le posizioni di 21 e 9
Il nuovo elenco è ora come sopra
Passaggio 3)
I valori 21 e 33 vengono confrontati per trovare quello maggiore.
Il valore 33 è maggiore di 21, quindi non viene eseguito alcuno scambio.
Passaggio 4)
I valori 33 e 3 vengono confrontati per trovare quello maggiore.
Il valore 33 è maggiore di 3, quindi scambiamo le loro posizioni.
L'elenco ordinato alla fine della prima iterazione è come quello sopra
Seconda iterazione
Il nuovo elenco dopo la seconda iterazione è il seguente
Terza iterazione
Il nuovo elenco dopo la terza iterazione è il seguente
Quarta iterazione
Il nuovo elenco dopo la quarta iterazione è il seguente
Esempi di Python
Il codice seguente mostra come implementare l'algoritmo Bubble Sort in Python.
def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)
L'esecuzione del suddetto programma di ordinamento delle bolle in Python produce i seguenti risultati
[6, 9, 21, 3, 33]
Spiegazione del codice
La spiegazione del codice del programma Python Bubble Sort è la seguente
QUI,
- Definisce una funzione bubbleSort che accetta un parametro theSeq. Il codice non restituisce nulla.
- Ottiene la lunghezza della matrice e assegna il valore a una variabile n. Il codice non restituisce nulla
- Avvia un ciclo for che esegue l'algoritmo di ordinamento delle bolle (n - 1) volte. Questo è il ciclo esterno. Il codice non restituisce nulla
- Definisce una variabile flag che verrà utilizzata per determinare se si è verificato o meno uno scambio. Questo è per scopi di ottimizzazione. Il codice non restituisce nulla
- Avvia il ciclo interno che confronta tutti i valori nell'elenco dal primo all'ultimo. Il codice non restituisce nulla.
- Utilizza l'istruzione if per verificare se il valore sul lato sinistro è maggiore di quello sul lato destro immediato. Il codice non restituisce nulla.
- Assegna il valore di theSeq [j] a una variabile temporale tmp se la condizione restituisce true. Il codice non restituisce nulla
- Il valore di theSeq [j + 1] è assegnato alla posizione di theSeq [j]. Il codice non restituisce nulla
- Il valore della variabile tmp viene assegnato alla posizione di theSeq [j + 1]. Il codice non restituisce nulla
- Alla variabile flag viene assegnato il valore 1 per indicare che è avvenuto uno scambio. Il codice non restituisce nulla
- Utilizza un'istruzione if per verificare se il valore del flag della variabile è 0. Il codice non restituisce nulla
- Se il valore è 0, allora chiamiamo l'istruzione break che esce dal ciclo interno.
- Restituisce il valore di theSeq dopo che è stato ordinato. Il codice restituisce l'elenco ordinato.
- Definisce una variabile el che contiene un elenco di numeri casuali. Il codice non restituisce nulla.
- Assegna il valore della funzione bubbleSort a un risultato variabile.
- Stampa il valore del risultato della variabile.
Vantaggi del Bubble sort
Di seguito sono riportati alcuni dei vantaggi dell'algoritmo di ordinamento delle bolle
- È facile da capire
- Funziona molto bene quando l'elenco è già o quasi ordinato
- Non richiede molta memoria.
- È facile scrivere il codice per l'algoritmo
- I requisiti di spazio sono minimi rispetto ad altri algoritmi di ordinamento.
Bubble sort Svantaggi
Di seguito sono riportati alcuni degli svantaggi dell'algoritmo di ordinamento delle bolle
- Non funziona bene quando si ordinano elenchi di grandi dimensioni. Ci vuole troppo tempo e risorse.
- Viene utilizzato principalmente per scopi accademici e non per applicazioni nel mondo reale.
- Il numero di passaggi necessari per ordinare l'elenco è dell'ordine n 2
Analisi della complessità del Bubble Sort
Esistono tre tipi di complessità:
1) Ordina complessità
La complessità dell'ordinamento viene utilizzata per esprimere la quantità di tempi di esecuzione e lo spazio necessari per ordinare l'elenco. L'ordinamento a bolle esegue (n - 1) iterazioni per ordinare l'elenco dove n è il numero totale di elementi nell'elenco.
2) Complessità temporale
La complessità temporale del Bubble Sort è O (n 2 )
Le complessità temporali possono essere classificate come:
- Nel peggiore dei casi : qui è dove l'elenco fornito è in ordine decrescente. L'algoritmo esegue il numero massimo di esecuzioni espresso come [Big-O] O (n 2 )
- Caso migliore : si verifica quando l'elenco fornito è già ordinato. L'algoritmo esegue il numero minimo di esecuzioni espresso come [Big-Omega] Ω (n)
- Caso medio : si verifica quando l'elenco è in ordine casuale. La complessità media è rappresentata come [Big-theta] ⊝ (n 2 )
3) Complessità spaziale
La complessità dello spazio misura la quantità di spazio aggiuntivo necessario per ordinare l'elenco. L'ordinamento a bolle richiede solo uno (1) spazio aggiuntivo per la variabile temporale utilizzata per lo scambio di valori. Pertanto, ha una complessità spaziale di O (1).
Sommario
- L'algoritmo di bubble sort funziona confrontando due valori adiacenti e scambiandoli se il valore a sinistra è inferiore al valore a destra.
- L'implementazione di un algoritmo di ordinamento delle bolle è relativamente semplice con Python. Tutto quello che devi usare sono i cicli for e le istruzioni if.
- Il problema che l'algoritmo di ordinamento delle bolle risolve è prendere un elenco casuale di elementi e trasformarlo in un elenco ordinato.
- L'algoritmo di ordinamento delle bolle nella struttura dei dati funziona al meglio quando l'elenco è già ordinato poiché esegue un numero minimo di iterazioni.
- L'algoritmo di ordinamento delle bolle non funziona bene quando l'elenco è in ordine inverso.
- L'ordinamento del bubbler ha una complessità temporale di O (n 2 ) e una complessità spaziale di O (1)
- L'algoritmo di ordinamento del bubbler è più adatto per scopi accademici e non per applicazioni del mondo reale.
- L'ordinamento a bolle ottimizzato rende l'algoritmo più efficiente saltando le iterazioni non necessarie durante il controllo dei valori che sono già stati ordinati.