Bubble sort è uno degli algoritmi di ordinamento più semplici. Si chiama bubble sort perché i valori saranno essa "bolla" nel proprio elenco verso l'alto (o in basso a seconda di come si pensa di esso). Mentre si tratta di una sorta di facile, ma non è così efficace come i tipi più avanzati, e in realtà dovrebbe essere utilizzato solo per scopi di apprendimento (se non si conosce l'elenco è quasi ordinato, nel qual caso non è male)

istruzione

1 Penso che il modo migliore per discutere di bubble sort è con un esempio. Darò una panoramica dell'algoritmo, e quindi lavoreremo con un esempio passo-passo per dare un'idea di come funziona. Quindi, prima, l'idea.

2 Bubble sort viene utilizzato per ordinare un elenco di elementi in ordine crescente o decrescente. Supponiamo per questo tipo che si desidera inserire l'elenco in ordine crescente (cioè 1,2,3, ecc.). L'ordinamento funziona passando sopra ogni elemento nella lista e confrontandola con l'elemento successivo nella lista. Se il primo elemento è maggiore del secondo elemento, i due sono commutati. Se il primo elemento è minore o uguale al secondo, non succede nulla. Dopo aver guardato questo elemento, l'elemento successivo si vede, e il processo si ripete.

3 Quando il tipo ha preso in esame ogni elemento, un 'passaggio' è stata completata. Dopo un passaggio, si sa per certo che un numero deve essere nella posizione corretta. Nel nostro ordine crescente, il valore più grande sara 'bolla' alla fine della lista. Purtroppo, non si sa se il resto della lista è ordinata, quindi bisogna prendere un altro passaggio. Tuttavia, su questo passaggio, ci si può fermare un elemento prima del termine poiché si sa che il numero è già nella posizione corretta.

4 Bubble sort (di solito) richiede diversi passaggi per completare. Il più passa esso richiederà è uguale al numero di elementi nella lista meno 1. Quindi, se si dispone di 10 elementi nel proprio elenco, potrebbe richiedere 9 passaggi per completare l'ordinamento. Andiamo attraverso un esempio per spiegare meglio.

5 Usiamo la seguente lista non ordinata:
6, 3, 1, 8, 2, 4

Vorremmo che la lista di simile a questa:
1, 2, 3, 4, 6, 8

Al primo passaggio, ci confrontare i numeri uno alla volta, e sappiamo che dopo un passaggio dovremmo avere il maggior numero completamente a destra, quindi in questo caso, che sarà 8. Per il nostro esempio, il segno ^ punterà al posto nella lista che stiamo attualmente esaminando.

6 6, 3, 1, 8, 2, 4

Passare 1, punto 1) Confrontare il 6 e il 3. 6 è maggiore di 3, in modo da noi li swap.
3, ^ 6, 1, 8, 2, 4

Passare 1, punto 2) Confrontare il 6 e il 1. 6 è maggiore di 1, quindi noi li swap.
3, 1, ^ 6, 8, 2, 4

Passare 1, punto 3) Confrontare il 6 e l'8 6 è inferiore o uguale a 8, in modo da non succede nulla.
3, 1, 6, 8 ^, 2, 4

Passare 1, punto 4) Confrontare l'8 e il 2. 8 è maggiore di 2, in modo da scambiare.
3, 1, 6, 2, ^ 8, 4

Passare 1, punto 5) Confrontare l'8 e il 4. 8 è superiore a 4, in modo da scambiare.
3, 1, 6, 2, 4, 8

E il gioco è fatto il primo passo!

7 3, 1, 6, 2, 4, 8 non è certo un elenco ordinato, ma si può vedere, come promesso, l'8 è alla fine. Io ora scrivere ciò che la lista si presenta come dopo ogni passaggio. Provate voi stessi, e vedere se il vostro partite la mia:
Passo 2: 1, 3, 2, 4, 6, 8 (guardando meglio)
Passare 3: 1, 2, 3, 4, 6, 8 (fatto)
Pass 4: 1, 2, 3, 4, 6, 8 (umm ... non sono stati abbiamo già fatto?)
Passa 5: 1, 2, 3, 4, 6, 8 (ancora fatto!)

8 Come si può vedere, l'elenco è stato risolto dopo 3 passaggi, ma il bubble sort continuato ad andare. Perché? Ebbene, l'algoritmo di base bubble sort è abbastanza stupida. Si vuole assicurarsi che funzioni nel caso peggiore (che è un elenco che è completamente all'indietro come 9, 8, 7, 6, 5). È possibile aggiungere una velocità fino a rendere il vostro bubble sort correre un po 'più veloce. Su ogni passaggio, una bandiera che viene impostata su true solo se effettivamente passa due numeri. Prima di fare il passo successivo, verificare se la bandiera è vera o falsa. Se è vero, è scambiato due numeri, e si deve fare un altro passaggio. Se è falso, l'elenco è ordinato, e si può essere fatto. Nel nostro esempio, anche se l'elenco è stato risolto dopo 3 passaggi, ci sarebbe ancora bisogno di fare un 4 ° passaggio perché abbiamo fatto uno swap nel 3 ° passaggio.

9 Ora sapete come fare un bubble sort. Lasciare commenti con tutte le domande che potreste avere. Grazie per aver letto!

Consigli e avvertenze

• Se si sta cercando di attuare bubble sort in un linguaggio di programmazione, e hai problemi, una matita e carta può aiutare a visualizzare ciò che l'algoritmo sta cercando di fare
• Ricordate, bubble sort non è una specie molto efficiente. Quindi, se avete bisogno di ordinare un elenco enorme, si dovrebbe guardare ad alcuni altri metodi.