[Powered by Google Translate] [BUBBLE SORT]
[JACKSON Steinkamp Harvard University]
[QUESTO E 'CS50. CS50TV]
Ordine bolla è un esempio di un algoritmo di ordinamento -
cioè, una procedura per l'ordinamento di un insieme di elementi in
ordine crescente o decrescente.
Per esempio, se si vuole ordinare un array costituito dai numeri
[3, 5, 2, 9], la corretta attuazione del Bubble Sort restituisce il
array ordinato [2, 3, 5, 9], in ordine crescente.
Ora, ho intenzione di spiegare in pseudocodice come funziona l'algoritmo.
>> Diciamo che stiamo ordinamento di una lista di 5 numeri interi - 3, 2, 9, 6, e 5.
L'algoritmo inizia esaminando i primi due elementi, 3 e 2,
e controllando se sono fuori ordine rispetto all'altra.
Sono - 3 è maggiore di 2.
Per essere in ordine crescente, che dovrebbe essere il contrario.
Quindi, li scambiare.
Ora la lista è simile al seguente: [2, 3, 9, 6, 5].
>> Quindi, guardiamo gli elementi secondo e il terzo, 3 e 9.
Sono nell'ordine corretto rispetto all'altro.
Cioè, 3 è inferiore a 9 quindi l'algoritmo non sostituirle.
Quindi, guardiamo alle 9 e 6. Sono fuori uso.
>> Quindi, abbiamo bisogno di scambiare loro, perché 9 è maggiore di 6.
Infine, guardiamo gli ultimi due numeri interi, 9 e 5.
Sono fuori di ordine, quindi devono essere scambiati.
Dopo il primo passaggio completa l'elenco,
che appare così: [2, 3, 6, 5, 9].
Non male. E 'quasi ordinato.
Ma abbiamo bisogno di scorrere la lista di nuovo per farlo completamente ordinato.
Due è inferiore a 3, quindi non li scambiare.
>> Tre è inferiore a 6, in modo da non li scambiare.
Sei è maggiore di 5. Ci scambiammo.
Sei è inferiore a 9. Noi non scambiare.
Dopo il secondo passaggio, che appare così: [2, 3, 5, 6, 9]. Perfetto.
Ora, cerchiamo di scrivere in pseudocodice.
In sostanza, per ogni elemento della lista, abbiamo bisogno di vedere le cose
e l'elemento direttamente alla sua destra.
Se essi non sono in ordine rispetto all'altra - cioè, se l'elemento a sinistra
è maggiore di quella di destra - dobbiamo scambiare i due elementi.
>> Lo facciamo per ogni elemento della lista, e abbiamo fatto un solo passaggio attraverso.
Ora non ci resta che fare il pass-through di volte sufficiente a garantire la lista
è completamente, opportunamente ordinati.
Ma quante volte dobbiamo passare attraverso l'elenco per
garantire che abbiamo finito?
Beh, la peggiore delle ipotesi è che se abbiamo una lista completamente all'indietro.
Poi prende un numero di pass-through pari al numero
di elementi di n-1.
Se questo non ha senso intuitivo, pensare ad un semplice caso - l'elenco [2, 1].
>> Si tratta di andare a prendere un pass-through per ordinare correttamente.
[3, 2, 1] - Il caso peggiore è che con 3 elementi ordinati al contrario,
sta andando a prendere 2 iterazioni da ordinare.
Dopo una iterazione, è [2, 1, 3].
Le rese secondo l'array ordinato [1, 2, 3].
Quindi sai che non deve passare attraverso la matrice, in generale,
più di n-1 volte, dove n è il numero di elementi nella matrice.
Si chiama Bubble Sort, perché gli elementi più grandi tendono a 'bubble-up'
a destra abbastanza rapidamente.
In realtà, questo algoritmo ha un comportamento molto interessante.
>> Dopo m iterazioni attraverso l'intero array,
gli elementi più a destra m sono garantiti
da ordinare nella loro posizione corretta.
Se volete vedere questo per te,
siamo in grado di provare in un elenco completamente all'indietro [9, 6, 5, 3, 2].
Dopo un passaggio attraverso l'intero elenco,
[Suono di scrittura]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
l'elemento più a destra 9 è al suo posto.
Dopo la seconda pass-through, il 6 avra 'bollito-up' al
secondo posto più a destra.
I due elementi a destra - 6 e 9 - sarà nelle loro posizioni corrette
dopo i primi due pass-through.
>> Quindi, come possiamo usare questo per ottimizzare l'algoritmo?
Bene, dopo un'iterazione attraverso l'array
in realtà non è necessario per controllare l'elemento più a destra
perché sappiamo che è ordinato.
Dopo due iterazioni, sappiamo per certo più a destra i due elementi sono in atto.
Quindi, in generale, dopo k iterazioni attraverso la matrice completa,
controllo degli elementi k ultimi è ridondante poiché sappiamo
sono nella posizione corretta già.
>> Quindi, se siete ordinamento di un array di n elementi,
alla prima iterazione - hai dovuto ordinare tutti gli elementi - il primo n-0.
Nella seconda iterazione, si dovrà esaminare tutti gli elementi, ma l'ultima -
il primo n-1.
Un'altra ottimizzazione potrebbe essere quello di verificare se la lista è già ordinato
dopo ogni iterazione.
Se è già ordinato, non abbiamo bisogno di fare più iterazioni
l'elenco.
Come possiamo fare questo?
Beh, se non si fa nessun swap su un pass-through della lista,
è chiaro che l'elenco è stato già ordinato perché non scambiare nulla.
Quindi sicuramente non c'è bisogno di ordinare di nuovo.
>> Forse si potrebbe inizializzare una variabile flag definito 'non ordinati' per
false e cambia a true se si deve scambiare qualsiasi altro elemento
un'iterazione attraverso l'array.
Oppure allo stesso modo, fare un contatore per contare il numero di operazioni di swap si fanno
su ogni iterazione determinato.
Al termine di una iterazione, se non scambiare qualsiasi degli elementi,
si conosce la lista è già ordinato e il gioco è fatto.
Bubble Sort, come altri algoritmi di ordinamento, può essere
ottimizzato per lavorare per tutti gli elementi che hanno un metodo di ordinamento.
>> In altre parole, dati due elementi si dispone di un modo per dire se il primo
è maggiore, uguale o minore della seconda.
Ad esempio, è possibile ordinare le lettere dell'alfabeto dicendo
che a <b, b <c, ecc
Oppure si potrebbe ordinare i giorni della settimana in cui Domenica è inferiore a Lunedi
che è inferiore Martedì.
>> Ordina Bubble non è affatto un algoritmo di ordinamento molto efficiente e veloce.
Il caso peggiore di runtime è Big O di n ²
perché si deve fare n iterazioni attraverso un elenco
controllare tutti gli elementi n ogni pass-through, nxn = n ².
Questa fase di esecuzione significa che il numero di elementi che stai ordinamento aumenta,
il tempo di esecuzione aumenta quadraticamente.
>> Ma se l'efficienza non è una preoccupazione importante del vostro programma
o se siete solo ordinare un piccolo numero di elementi,
si potrebbe trovare Bubble Sort utile perché
è uno dei più semplici algoritmi di ordinamento per capire
e per codice.
E 'anche un ottimo modo per ottenere esperienza con traduzione di un teorico
algoritmo in codice reale funzionamento.
Beh, e 'Bubble Sort per voi. Grazie per la visione.
CS50.TV