>> [RIPRODUZIONE DI BRANI MUSICALI]
DOUG LLOYD: Va bene, allora bubble sort è un algoritmo
è possibile utilizzare per ordinare un insieme di elementi.
Diamo uno sguardo a come funziona.
>> L'idea di base dietro bubble sort è questo.
In genere vogliamo andare più alto Elementi valutati generalmente a destra,
e abbassare elementi valutati in generale a sinistra, come ci aspetteremmo.
Vogliamo che le cose inferiori di essere al All'inizio, e le cose più elevate
per essere alla fine.
>> Come facciamo questo?
Bene in codice pseudocodice, potremmo dire, andiamo
impostare un contatore swap per un valore diverso da zero.
Vedremo perché lo facciamo in un secondo.
E poi si ripete il seguente processo fino a quando il contatore swap è 0,
o fino a quando non facciamo swap a tutti.
>> Azzerare il contatore swap 0 se non è già 0.
Poi guardate ogni coppia adiacente di elementi.
Se questi due elementi sono non in ordine, scambiarle,
e aggiungere 1 al contatore di swap.
Se stai pensando di questo prima di visualizzarlo,
si noti che questo si muoverà più basso elementi valutati a sinistra
e superiore valutati elementi alla destra, effettivamente fare quello che vogliamo fare,
che è spostare i gruppi di elementi in questo modo.
Cerchiamo di visualizzare come questo potrebbe apparire con la nostra gamma
che abbiamo usato per testare questi algoritmi.
Abbiamo un array non ordinato di nuovo qui, indicata con tutti gli elementi
essendo in rosso.
E ho impostato il mio contatore di swap ad un valore diverso da zero.
Ho scelto arbitrariamente negativo 1-- non è 0.
Vogliamo ripetere questo processo fino a quando il contatore di swap è 0.
Questo è il motivo per cui ho impostato la mia di swap contatore su un valore diverso da zero,
perché altrimenti la contatore di scambio sarebbe 0.
Non avremmo nemmeno cominciare il processo dell'algoritmo.
Quindi, di nuovo, i passi are-- azzerare il contatore di scambio
a 0, poi guardare ogni adiacente coppia, e se sono in ordine,
scambiarli, e aggiungere 1 al contatore swap.
Quindi cerchiamo di iniziare questo processo.
Quindi la prima cosa che facciamo è abbiamo impostato il contatore di scambio a 0,
e poi si parte alla ricerca ad ogni coppia adiacente.
>> Quindi per prima cosa iniziamo guardando 5 e 2.
Vediamo che sono fuori Ordine e così li scambiamo.
E aggiungiamo 1 al bancone di swap.
Così ora il nostro contatore di scambio è 1, e 2 e 5 sono stati passati.
Ora ripetiamo di nuovo il processo.
>> Guardiamo alla prossima coppia adiacente, 5 e 1-- sono anche in ordine,
così noi li scambiamo e aggiungere 1 al contatore swap.
Poi guardiamo 5 e 3.
Essi sono in ordine, in modo da scambiare li e ci aggiungi 1 al bancone di swap.
Poi guardiamo 5 e 6.
Sono in ordine, in modo che in realtà non hanno bisogno di scambiare nulla questa volta.
Poi guardiamo 6 e 4.
Sono anche fuori ordine, in modo da scambiare li e ci aggiungi 1 al bancone di swap.
>> Ora notate quello che è successo.
Abbiamo spostato 6 fino alla fine.
Quindi, in selezione tipo, se hai visto che il video, quello che abbiamo fatto è stato
abbiamo finito per spostare il elementi più piccoli in edilizia
l'array ordinato essenzialmente da da sinistra a destra, piccolo al più grande.
Nel caso di bubble sort, se siamo seguendo questo particolare algoritmo,
realmente stiamo andando a costruire l'array ordinato da destra
a sinistra, la più grande al più piccolo.
Abbiamo effettivamente bolle 6, il valore più grande, fino alla fine.
>> E così ora possiamo dichiarare che che è ordinato,
e in futuro iterations-- passando attraverso l'array again--
non dobbiamo considerare 6 più.
Dobbiamo solo prendere in considerazione gli elementi sottoposti a cernita
quando stiamo guardando coppie adiacenti.
Così abbiamo finito uno passare attraverso bubble sort.
Così ora torniamo alla domanda, ripetere fino a quando il contatore di scambio è 0.
Bene il contatore di scambio è 4, quindi stiamo andando
continuare a ripetere di nuovo il processo.
>> Stiamo per azzerare il contatore di scambio a 0, e guardare ogni coppia adiacente.
Quindi si parte con 2 e 1-- sono fuori uso, così li scambiamo
e aggiungiamo 1 al bancone di swap.
2 e 3, sono in ordine.
Non abbiamo bisogno di fare nulla.
3 e 5 sono in ordine.
Non abbiamo bisogno di fare nulla.
>> 5 e 4, sono fuori di ordine, e così noi
necessario per scambiarle e aggiungere 1 al contatore swap.
E ora ci siamo spostati 5, il successivo elemento più grande,
alla fine della porzione indifferenziati.
Così ora possiamo chiamare quella parte della porzione filtrate.
>> Ora si sta guardando la schermo e probabilmente può dire,
come posso, che l'array è ordinato al momento.
Ma non possiamo dimostrare ancora che.
Non abbiamo una garanzia che è ordinato.
Ma questo è dove lo swap contatore sta per entrare in gioco.
>> Così abbiamo completato un passaggio.
Il contatore swap è 2.
Così stiamo andando a ripetere nuovo questo processo,
ripetere fino a quando il contatore di scambio è 0.
Azzerare il contatore di scambio a 0.
Quindi dovremo resettarlo.
>> Ora guardate ogni coppia adiacente.
Questo è in ordine, 1 e 2.
2 e 3 sono in ordine.
3 e 4 sono in ordine.
Quindi a questo punto, notiamo abbiamo completato guardando ogni coppia adiacente,
ma il contatore di scambio è ancora 0.
>> Se non abbiamo passare elementi, allora
deve essere in ordine, dal virtù di questo processo.
E così un rendimento di sorta, che gli scienziati ci informatici amano,
è ora possiamo dichiarare l'intero array deve
essere ordinati, perché non abbiamo fatto avere scambiare elementi.
Questo è abbastanza piacevole.
>> Allora qual è il caso peggiore scenario con bubble sort?
Nel peggiore dei casi la matrice è in ordine completamente inverso,
e quindi dobbiamo bolla ogni dei grandi elementi tutti
il senso attraverso l'array.
E abbiamo efficacemente anche a bolla tutti i piccoli elementi indietro
tutto il senso attraverso l'array, anche.
Così ciascuno degli n elementi deve spostare in tutti gli altri elementi n.
Ecco, questo è lo scenario peggiore.
Nel migliore dei casi scenario però, questo è
leggermente diverso da selection sort.
La matrice è già ordinato quando andiamo in.
Noi non dobbiamo fare alcun swap sul primo passaggio.
Così potremmo avere a guardare in minor numero di elementi, giusto?
Noi non dobbiamo ripetere questo elaborare un certo numero di volte.
>> Che cosa significa?
Quindi qual è la peggiore delle ipotesi per bubble sort, e ciò che è
la migliore delle ipotesi per il bubble sort?
Hai fatto a indovinare questo?
Nel peggiore dei casi si deve iterare in tutti gli n elementi n volte.
Così il caso peggiore è n quadrato.
>> Se la matrice è perfettamente ordinato, però, è solo
guardare a ogni degli elementi una volta.
E se il contatore di scambio è ancora 0, si può dire che questo array è ordinato.
E così nel migliore dei casi, si tratta in realtà meglio di selezione
sort-- è omega di n.
>> Sono Doug Lloyd.
Questo è CS50.