Bubble Algoritmo di ordinamento con Python utilizzando l'esempio di elenco

Che cos'è un Bubble Ordina?

Bubble Ordina è 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 occupa la posizione del secondo valore, mentre il secondo valore occupa la posizione del primo valore. Se il primo valore è inferiore al secondo valore, non viene effettuato alcuno scambio.

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:

L'implementazione di Bubble Algoritmo di ordinamento

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 elementi in ordine casuale e vorremmo disporre gli elementi in modo ordinato

Considerate il seguente elenco:

[21,6,9,33,3]

La soluzione

Scorrere l'elenco confrontando due elementi adiacenti e scambiandoli se il primo valore è superiore al secondo valore.

Il risultato dovrebbe essere il seguente:

[3,6,9,21,33]

Algoritmo

L'algoritmo di ordinamento delle bolle funziona come segue

Passo 1) Ottieni il numero totale di elementi. Ottieni il numero totale di elementi nell'elenco fornito

Passo 2) Determinare il numero di passaggi esterni (n – 1) da eseguire. La sua lunghezza è lista meno uno

Passo 3) Esegui i passaggi interni (n – 1) volte per il passaggio esterno 1. Ottieni il valore del primo elemento e confrontalo con il secondo valore. Se il secondo valore è inferiore al primo valore, scambia le posizioni

Passo 4) Ripetere i passaggi del 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 corretto ordine crescente.

Passo 5) Restituisce il risultato quando tutti i passaggi sono stati eseguiti. Restituisce i risultati dell'elenco ordinato

Passo 6) Ottimizza 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 eseguita utilizzando i seguenti passaggi

Passo 1) Crea una variabile flag che monitora se si è verificato uno scambio nel ciclo interno

Passo 2) Se i valori hanno scambiato le posizioni, continuare con l'iterazione successiva

Passo 3) Se i benefici non si sono scambiati di posizione, termina il ciclo interno e continua con quello esterno.

Un bubble sort ottimizzato è più efficiente poiché esegue solo i passaggi necessari e salta quelli non richiesti.

Rappresentazione visiva

Dato un elenco di cinque elementi, le immagini seguenti illustrano come l'ordinamento a bolle itera attraverso 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 invertiamo le posizioni di 21 e 9

Il nuovo elenco è ora come sopra

Passo 3)

I valori 21 e 33 vengono confrontati per trovare quello maggiore.

Il valore 33 è maggiore di 21, quindi non avviene alcuno scambio.

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 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

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

[6, 9, 21, 3, 33]

Spiegazione del codice

La spiegazione per il Python Bubble L'ordinamento del codice del programma è il seguente

QUI,

1. Definisce una funzione bubbleSort che accetta un parametro theSeq. Il codice non restituisce nulla.
2. Ottiene la lunghezza dell'array e assegna il valore a una variabile n. Il codice non restituisce nulla
3. Avvia un ciclo for che esegue l'algoritmo di bubble sort (n – 1) volte. Questo è il circuito esterno. Il codice non restituisce nulla
4. Definisce una variabile flag che verrà utilizzata per determinare se si è verificato uno scambio o meno. Questo è per scopi di ottimizzazione. Il codice non restituisce nulla
5. Avvia il ciclo interno che confronta tutti i valori nell'elenco dal primo all'ultimo. Il codice non produce nulla.
6. Utilizza l'istruzione if per verificare se il valore sul lato sinistro è maggiore di quello sul lato immediatamente destro. Il codice non restituisce nulla.
7. Assegna il valore di theSeq[j] a una variabile temporale tmp se la condizione risulta vera. Il codice non restituisce nulla
8. Il valore di theSeq[j + 1] è assegnato alla posizione di theSeq[j]. Il codice non restituisce nulla
9. Il valore della variabile tmp è assegnato alla posizione theSeq[j + 1]. Il codice non restituisce nulla
10. Alla variabile flag viene assegnato il valore 1 per indicare che ha avuto luogo uno scambio. Il codice non restituisce nulla
11. Utilizza un'istruzione if per verificare se il valore del flag variabile è 0. Il codice non restituisce nulla
12. Se il valore è 0, chiamiamo l'istruzione break che esce dal ciclo interno.
13. Restituisce il valore di theSeq dopo che è stato ordinato. Il codice restituisce l'elenco ordinato.
14. Definisce una variabile el che contiene un elenco di numeri casuali. Il codice non restituisce nulla.
15. Assegna il valore della funzione bubbleSort a un risultato variabile.
16. Stampa il valore del risultato della variabile.

Bubble sorta di vantaggi

Di seguito sono riportati alcuni dei vantaggi dell'algoritmo bubble sort

• È facile da capire
• Funziona molto bene quando l'elenco è già o quasi ordinato
• 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 riportati alcuni degli svantaggi dell'algoritmo bubble sort

• 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 la lista è dell'ordine n²

Analisi della complessità di Bubble Ordina

Esistono tre tipi di complessità:

1) Ordina la complessità

La complessità di ordinamento è utilizzata per esprimere la quantità di tempi di esecuzione e spazio necessari per ordinare l'elenco. Il bubble sort esegue (n – 1) iterazioni per ordinare l'elenco, dove n è il numero totale di elementi nell'elenco.

2) Complessità temporale

La complessità temporale dell'ordinamento a bolle è O(n²)

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(n²)
• caso migliore – questo avviene 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] ⊝(n²)

3) Complessità dello spazio

La complessità spaziale misura la quantità di spazio extra necessaria per ordinare l'elenco. Il bubble sort richiede solo uno (1) spazio extra per la variabile temporale utilizzata per lo scambio di valori. Pertanto, ha una complessità spaziale di O (1).

Sintesi

• L'algoritmo di ordinamento delle bolle funziona confrontando due valori adiacenti e scambiandoli se il valore a sinistra è inferiore al valore a destra.
• L'implementazione di un algoritmo di ordinamento a bolle è relativamente semplice con Python. Tutto quello che devi usare sono i cicli for e le istruzioni if.
• Il problema risolto dall'algoritmo Bubble Sort è prendere un elenco casuale di elementi e trasformarlo in un elenco ordinato.
• L'algoritmo di ordinamento a bolle nella struttura dei dati offre prestazioni migliori 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 bubbler ha una complessità temporale di O (n²) e una complessità spaziale di O (1)
• L'algoritmo di ordinamento bubbler è più adatto per scopi accademici e non per applicazioni nel mondo reale.
• L'ordinamento a bolle ottimizzato rende l'algoritmo più efficiente saltando iterazioni non necessarie durante il controllo dei valori che sono già stati ordinati.