[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