Bubble Algoritmo di ordinamento con Python utilizzando l'esempio di elenco
Sara Chen
⚡ Riepilogo intelligente
Bubble Sort ordina gli elementi della lista in ordine crescente confrontando ripetutamente i valori adiacenti e scambiandoliping quando l'elemento a sinistra è più grande. Questo semplice ordinamento per confronto è adatto a set di dati piccoli o quasi ordinati e insegna efficacemente la logica di ordinamento di base.
Che cos'è un Bubble Ordina?
Bubble Ordina è un algoritmo di ordinamento utilizzato per ordinare gli elementi di una lista in ordine crescente confrontando due valori adiacenti. Se il primo valore è maggiore del secondo, il primo valore prende la posizione del secondo, mentre il secondo valore prende la posizione del primo. Se il primo valore è minore del secondo, non avviene alcuno scambio.ping è fatta.
Questo processo viene ripetuto finché tutti i valori in un elenco non sono stati confrontati e scambiati, se necessario. 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 questa Bubble Ordinamento Python lezione imparerai il problema che risolve, la sua forma ottimizzata, una guida visiva passo passo, un funzionamento Python programma e le sue caratteristiche prestazionali.
L'implementazione di Bubble Algoritmo di ordinamento
Suddivideremo l'implementazione in tre (3) fasi, vale a dire il problema, la soluzione e l'algoritmo che possiamo usare per scrivere codice per qualsiasi linguaggio.
Il problema
Viene fornito un elenco di elementi in ordine casuale e vorremmo disporli in modo ordinato.
Considerate il seguente elenco:
[21, 6, 9, 33, 3]
La soluzione
Scorri la lista confrontando due elementi adiacenti e scambialiping se il primo valore è maggiore del secondo valore.
Il risultato dovrebbe essere il seguente:
[3, 6, 9, 21, 33]
Algoritmo
L'algoritmo di ordinamento a bolle funziona nel seguente modo:
Passo 1) Ottieni il numero totale di elementi. Ottieni il numero totale di elementi nell'elenco dato.
Passo 2) Determinare il numero di passaggi esterni (n – 1) da eseguire. La sua lunghezza è list meno uno.
Passo 3) Eseguire passaggi interni (n – 1) volte per il passaggio esterno 1. Ottenere il valore del primo elemento e confrontarlo con il secondo valore. Se il secondo valore è minore del primo, scambiare le posizioni.
Passo 4) Ripeti il passaggio 3 fino a raggiungere il passaggio più esterno (n – 1). Prendi l'elemento successivo nell'elenco, quindi ripeti il processo eseguito al passaggio 3 finché tutti i valori non saranno stati disposti nel loro corretto ordine crescente.
Passo 5) Restituisci il risultato al termine di tutti i passaggi. Restituisci i risultati dell'elenco ordinato.
Passo 6) Ottimizzazione dell'algoritmo.
Evitare 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, possiamo interrompere il ciclo in anticipo.
Ottimizzato Bubble Algoritmo di ordinamento
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 specificato è già ordinato, confrontare tutti i valori è uno spreco 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 viene avviata quella successiva fino al completamento del processo come mostrato di seguito Bubble Esempio di ordinamento.
L'ottimizzazione viene effettuata seguendo questi passaggi:
Passo 1) Crea una variabile flag che monitora se c'è uno scambioping si è verificato nel ciclo interno.
Passo 2) Se i valori si sono scambiati di posizione, procedere all'iterazione successiva.
Passo 3) Se i valori non si sono scambiati di posizione, termina il ciclo interno e continua con il ciclo esterno.
Un bubble sort ottimizzato è più efficiente poiché esegue solo i passaggi necessari e salta quelli non richiesti.
Rappresentazione visiva
Data una lista di cinque elementi, le immagini seguenti illustrano come l'algoritmo di ordinamento a bolle scorre i 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 è 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 quello sopra indicato.
Passo 3)
I valori 21 e 33 vengono confrontati per trovare quello maggiore.
Il valore 33 è maggiore di 21, quindi non c'è scambioping si svolge.
Passo 4)
I valori 33 e 3 vengono confrontati per trovare quello maggiore.
Il valore 33 è maggiore di 3, quindi invertiamo le loro posizioni.
L'elenco ordinato al termine della prima iterazione è simile a 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:
Python Esempi
Il codice seguente mostra come implementare il Bubble Algoritmo di ordinamento in Python.
def bubbleSort(theSeq): n = len(theSeq) for i in range(n - 1): flag = 0 for j in range(n - 1): if theSeq[j] > theSeq[j + 1]: tmp = theSeq[j] theSeq[j] = theSeq[j + 1] theSeq[j + 1] = tmp flag = 1 if flag == 0: break return theSeq el = [21, 6, 9, 33, 3] result = bubbleSort(el) print(result)
Esecuzione del programma di ordinamento a bolle sopra riportato in Python produce i seguenti risultati:
[3, 6, 9, 21, 33]
Code Spiegazione
La spiegazione per il Python BubblIl codice del programma di ordinamento è il seguente:
QUI,
- Definisce una funzione bubbleSort che accetta un parametro theSeq. Il codice non restituisce nulla.
- Recupera la lunghezza dell'array e assegna il valore a una variabile n. Il codice non produce alcun output.
- Avvia un ciclo for che esegue l'algoritmo di ordinamento a bolle (n – 1) volte. Questo è il ciclo esterno. Il codice non produce alcun output.
- Definisce una variabile flag che verrà utilizzata per determinare se si è verificato uno scambio o meno. Questo serve a fini di ottimizzazione. Il codice non produce alcun output.
- Avvia il ciclo interno che confronta tutti i valori nell'elenco dal primo all'ultimo. Il codice non produce nulla.
- Utilizza l'istruzione if per verificare se il valore sul lato sinistro è maggiore di quello sul lato immediatamente destro. Il codice non restituisce nulla.
- Assegna il valore di theSeq[j] a una variabile temporale tmp se la condizione risulta vera. Il codice non produce alcun output.
- Il valore di theSeq[j + 1] viene assegnato alla posizione di theSeq[j]. Il codice non produce alcun output.
- Il valore della variabile tmp viene assegnato alla posizione theSeq[j + 1]. Il codice non produce alcun output.
- Alla variabile flag viene assegnato il valore 1 per indicare che è avvenuto uno scambio. Il codice non produce alcun output.
- Utilizza un'istruzione if per verificare se il valore della variabile flag è 0. Il codice non produce alcun output.
- Se il valore è 0, 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.
Bubble sorta di vantaggi
Di seguito sono elencati alcuni dei vantaggi dell'algoritmo di ordinamento a bolle:
- È facile da capire
- Funziona molto bene quando l'elenco è già ordinato o quasi.
- Non richiede memoria estesa.
- È facile scrivere il codice per l'algoritmo.
- I requisiti di spazio sono minimi rispetto ad altri algoritmi di ordinamento.
Bubble ordinare Svantaggi
Di seguito sono elencati alcuni degli svantaggi dell'algoritmo di ordinamento a bolle:
- Non funziona bene quando si ordinano elenchi di grandi dimensioni. Ci vuole troppo tempo e risorse.
- Viene utilizzato principalmente a fini accademici e non per applicazioni pratiche nel mondo reale.
- Il numero di passaggi necessari per ordinare la lista è dell'ordine n2.
Analisi della complessità di Bubble Ordina
Esistono tre tipi di complessità:
1) Ordina la complessità
La complessità dell'ordinamento viene utilizzata per esprimere la quantità di tempo di esecuzione e di spazio necessari per ordinare la lista. L'algoritmo Bubble Sort effettua (n – 1) iterazioni per ordinare la lista, dove n è il numero totale di elementi nella lista.
2) Complessità temporale
La complessità temporale dell'ordinamento a bolle è O(n2).
Le complessità temporali possono essere classificate come:
- Caso peggiore – qui è dove l'elenco fornito è in ordine decrescente. L'algoritmo esegue il numero massimo di esecuzioni espresso come [Big-O] O(n2).
- caso migliore – ciò si verifica quando l'elenco fornito è già ordinato. L'algoritmo esegue il numero minimo di esecuzioni che è espresso come [Big-Omega] Ω(n).
- Caso medio – questo accade quando l'elenco è in ordine casuale. La complessità media è rappresentata come [Big-theta] ⊝(n2).
3) Complessità dello spazio
La complessità dello spazio misura la quantità di spazio extra necessaria per ordinare la lista. L'ordinamento a bolle richiede solo uno (1) spazio extra per la variabile temporale utilizzata per lo scambioping valori. Pertanto, ha una complessità spaziale di O(1).
