>> [MUSIC JOC]
DOUG LLOYD: Bine, așa bule fel este un algoritm
puteți utiliza pentru a sorta un set de elemente.
Să aruncăm o privire la modul în care funcționează.
>> Deci, ideea de bază din spatele bubble fel este aceasta.
Noi, în general doresc să se deplaseze mai mare elemente de valoare, în general, la dreapta,
și coborâți elemente evaluate, în general, la stânga, așa cum ne-am aștepta.
Ne dorim lucrurile mai mici pentru a fi la la început, și lucrurile mai mari
să fie la sfârșitul anului.
>> Cum facem acest lucru?
Ei bine, în codul pseudocod, am putea spune, să
stabilit un contor de schimb la o valoare diferită de zero.
Vom vedea ce vom face acest lucru într-o secundă.
Și apoi ne-am repeta următoarele proces până când contorul de swap este 0,
sau până când vom face nici un swap-uri, la toate.
>> Reseta contorul de swap pentru a 0 daca nu e deja 0.
Apoi uita-te la fiecare pereche adiacentă de elemente.
Dacă aceste două elemente sunt nu în ordine, le schimba,
și se adaugă 1 la ghișeul de schimb.
Dacă te gândești acest înainte de a le vizualiza,
observați că acest lucru va muta mai mici elemente evaluate la stânga
și mai mari elemente la dreapta de prim rang, face în mod eficient ceea ce vrem să facem,
care este muta acele grupuri de elemente în acest fel.
Să vizualiza modul în care acest s-ar putea uita-te folosind gama noastră
care am folosit pentru a testa aceste algoritmi.
Avem o gamă nesortate aici, din nou, indicat prin toate elementele
fiind în roșu.
Și am pus contra mea de schimb la o valoare diferită de zero.
Am ales în mod arbitrar negativ 1-- nu este 0.
Ne dorim să se repete acest proces până contorul de swap este 0.
Acesta este motivul pentru care am stabilit de swap meu în contradicție cu o valoare diferită de zero,
pentru ca altfel contor de swap ar fi 0.
Noi nici măcar nu s-ar începe proces a algoritmului.
Deci, din nou, pașii are-- reseta contorul de swap
la 0, apoi uita-te la fiecare adiacente pereche, iar în cazul în care acestea sunt de ordine,
swap-le, și se adaugă 1 la ghișeul de schimb.
Așa că haideți să începem acest proces.
Deci, primul lucru ce facem este ne-am stabilit contorul de swap la 0,
și apoi vom începe căutarea la fiecare pereche adiacentă.
>> Deci, vom începe mai întâi căutarea la 5 și 2.
Vedem că acestea sunt în afara comandă și așa le-am schimba.
Și vom adăuga 1 la contorul de swap.
Deci, acum contra noastră de swap este de 1, și 2 și 5 au fost pornit.
Acum vom repeta din nou acest proces.
>> Ne uităm la următoarea pereche adiacentă, 5 și 1-- sunt, de asemenea, din ordin,
asa ca am le schimba și se adaugă 1 la contorul de swap.
Apoi ne uităm la 5 și 3.
Ele sunt în afara de ordine, asa ca am schimba ei și vom adăuga 1 la contorul de swap.
Apoi ne uităm la 5 și 6.
Sunt în ordine, așa că nu face de fapt Trebuie să schimb ceva de data asta.
Apoi ne uităm la 6 și 4.
Sunt, de asemenea, din ordin, asa ca am schimba ei și vom adăuga 1 la contorul de swap.
>> Acum observați ce sa întâmplat.
Ne-am mutat 6 tot drumul până la sfârșit.
Deci, în alegerea fel, dacă ați văzut că video, ceea ce am făcut a fost
am ajuns deplasând mai mici elemente în clădire
matrice sortate, în esență, de la la stânga la dreapta, mai mic la cel mai mare.
În cazul bule fel, dacă suntem în urma acestui algoritm special,
ne de fapt, va fi construirea matrice sortate de la dreapta
la stânga, cel mai mare la cel mai mic.
Am barbotat efectiv lui 6, cea mai mare valoare, tot drumul până la sfârșit.
>> Și astfel încât să putem declara acum că este sortată,
și în viitor iterations-- trece prin matrice again--
noi nu trebuie să ia în considerare mai 6.
Trebuie doar să ia în considerare elementele nesortate
când ne uităm la perechi adiacente.
Deci, ne-am terminat unul trece prin balon fel.
Deci, acum ne întoarcem la întrebarea, repetă până când contorul de swap este 0.
Ei bine, contra schimb este de 4, asa ca vom
a repeta din nou acest proces.
>> Mergem pentru a reseta contorul de swap la 0, si uita-te la fiecare pereche adiacentă.
Deci, vom începe cu 2 și 1-- sunt din ordin, asa ca le-am schimba
și vom adăuga 1 la contorul de swap.
2 și 3, sunt în ordine.
Noi nu trebuie să facem nimic.
3 și 5 sunt în ordine.
Noi nu trebuie să facem nimic acolo.
>> 5 și 4, acestea sunt în afara de ordine, și așa ne-am
Trebuie să le schimba și se adaugă 1 la contorul de swap.
Și acum ne-am mutat 5, următoarea cea mai mare element,
la sfârșitul porțiunii nesortate.
Deci, putem apela acum că parte a porțiunii sortate.
>> Acum sunteți în căutarea la Cinema și, probabil, pot spune,
cum aș putea, ca matrice este sortata acum.
Dar nu putem dovedi că încă.
Noi nu avem o garanție că este sortate.
Dar acest lucru este în cazul în care swap- contra va intra în joc.
>> Deci, am finalizat o pasă.
Contorul de swap este de 2.
Așa că am de gând să repet acest proces, din nou,
repetă până când contorul de swap este 0.
Reseta contorul de swap la 0.
Deci vom reseta.
>> Acum uita-te la fiecare pereche adiacentă.
Asta e în ordine, 1 și 2.
2 și 3 sunt în ordine.
3 și 4 sunt în ordine.
Deci, la acest punct, ne-am completat observa uita la fiecare pereche adiacentă,
dar contorul de swap este încă 0.
>> Dacă nu avem pentru a comuta orice elemente, atunci ele
trebuie să fie în ordine, de virtutea acestui proces.
Și astfel o eficiență de soiuri, că oameni de știință de calculator ne place,
este putem declara acum întreaga rețea trebuie să
fi sortate, pentru că nu am Trebuie să schimb elemente.
Asta e destul de frumos.
>> Deci, ce este cel mai rău caz scenariu cu bule fel?
În cel mai rău caz matrice este în ordine inversă complet,
și așa că trebuie să bule fiecare a elementelor mari tot
drumul peste matrice.
Și în mod eficient, de asemenea, să avem balon toate elementele mici din spate
tot drumul peste matrice, de asemenea.
Deci fiecare dintre cele n elemente trebuie să se deplaseze in toate celelalte n elemente.
Deci, asta e cel mai rău caz.
În cel mai bun caz scenariu deși, aceasta este
ușor diferite de selecție fel.
Matrice este deja clasificate în funcție atunci când vom merge în.
Noi nu avem de a face orice swap-uri pe prima trecere.
Deci, am putea avea să te uiți la mai puține elemente, nu?
Noi nu trebuie să repetați acest procesa un număr de ori peste.
>> Deci, ce înseamnă asta?
Deci, ce este cel mai rău caz pentru bule de sortare, și ceea ce este
cel mai bun caz pentru bule fel?
Ai ghicit asta?
În cel mai rău caz, trebuie să repeta în toate elementele n n ori.
Deci cel mai rău caz este n pătrat.
>> În cazul în care matricea este perfect sortat deși, doar
trebuie să se uite la fiecare a elementelor dată.
Și dacă contorul de swap este încă 0, vă pot spune acest lucru este matrice sortate.
Și astfel, în cel mai bun caz, acest lucru este de fapt, mai bine decât de selecție
sort-- este omega de n.
>> Sunt Doug Lloyd.
Acest lucru este CS50.