[Powered by Google Translate] [SORT BUBBLE]
[JACKSON Steinkamp Universitatea Harvard]
[THIS IS CS50. CS50TV]
Sortare Bubble este un exemplu de algoritm de sortare -
că este, o procedură de sortare un set de elemente în
ordine crescătoare sau descrescătoare.
De exemplu, dacă ai vrut să sortați o matrice format din numere
[3, 5, 2, 9], o punere în aplicare corectă a după Bubble ar reveni
matrice sortate [2, 3, 5, 9], în ordine crescătoare.
Acum, am de gând să explice în pseudocod algoritmul functioneaza cum.
>> Să spunem că te sortarea o listă de 5 intregi - 3, 2, 9, 6, și 5.
Algoritmul începe uitandu-se la primele două elemente, 3 și 2,
și verificarea dacă sunt în ordine față de celălalt.
Acestea sunt - 3 este mai mare de 2.
Pentru a fi în ordine crescătoare, acestea ar trebui să fie invers.
Deci, i-am schimba.
Acum, lista arată astfel: [2, 3, 9, 6, 5].
>> În continuare, ne uităm la elementele doilea și al treilea, 3 și 9.
Sunt în ordinea corectă față de celălalt.
Asta este, 3 este mai mică de 9, astfel algoritmul nu le schimba.
În continuare, ne uităm la 9 și 6. Sunt de ordine.
>> Deci, avem nevoie de a le schimba, deoarece 9 este mai mare de 6.
În cele din urmă, ne uităm la ultimele două numere întregi, 9 și 5.
Sunt de ordine, astfel încât acestea trebuie să fie schimbate.
După trecere completă prin prima listă,
se pare ca acest lucru: [2, 3, 6, 5, 9].
Nu-i rău. E aproape sortate.
Dar avem nevoie pentru a rula prin lista din nou să-l complet sortate.
Doi este mai mică de 3, așa că nu le schimba.
>> Trei este mai mică de 6, așa că nu le schimba.
Sase este mai mare decât 5. Am schimbat.
Sase este mai mică de 9. Noi nu schimba.
Dupa a doua trecere prin, se pare ca aceasta: [2, 3, 5, 6, 9]. Eveniment.
Acum, hai să-l scrie în pseudocod.
Practic, pentru fiecare element în listă, trebuie să ne uităm la ea
și elementul direct la dreptul său.
În cazul în care acestea sunt în afara de ordine față de celălalt - că este, în cazul în care elementul de pe partea stângă
este mai mare decât cea de pe dreapta - ar trebui să ne schimba cele două elemente.
>> Noi facem acest lucru pentru fiecare element al listei, iar noi am făcut-o singură trecere prin.
Acum trebuie doar să facă ori trec prin destule-pentru a asigura listă
este complet, corect sortate.
Dar cum de multe ori avem de a trece prin lista de la
garanteze că am terminat?
Ei bine, scenariul cel mai rău caz este dacă avem o listă complet invers.
Apoi, este nevoie de un număr de pass-through egal cu numărul
de elemente n-1.
Dacă acest lucru nu are nici un sens intuitiv, cred că de un simplu caz - lista [2, 1].
>> Acest lucru se întâmplă pentru a lua una de trecere pentru a sorta corect.
[3, 2, 1] - cel mai grav caz este că, cu 3 elemente sortate invers,
se va lua 2 iterații la fel.
După un iterație, e [2, 1, 3].
Randamentele două matrice sortate [1, 2, 3].
Deci, știți că niciodată nu trebuie să treacă prin matrice, în general,
mai mult n-1 de ori, unde n este numărul de elemente din matrice.
Se numește după Bubble, deoarece cele mai mari elemente au tendința de a "balon-up"
la dreapta destul de repede.
De fapt, acest algoritm are un comportament foarte interesant.
>> După ce m iterații prin matrice întregul,
elementele din dreapta m sunt garantate
care urmează să fie sortate în locul lor corectă.
Dacă vrei să vezi asta pentru tine,
putem încerca pe o listă complet în spate [9, 6, 5, 3, 2].
După o singură trecere prin întreaga listă,
[Sunet de scris]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
elementul cel mai din dreapta 9 este în locul său.
După al doilea pass-through, 6 va avea "barbotat-up" la
două din dreapta loc.
Cele două elemente de pe dreapta - 6 și 9 - va fi în locurile lor corecte
după primele două pass-through.
>> Deci, cum putem folosi aceasta pentru a optimiza algoritmul?
Ei bine, după o iterație prin matrice
nu avem nevoie de fapt, pentru a verifica elementul cel mai din dreapta
pentru că știm că e sortate.
După două iterații, știm sigur că din dreapta două elemente sunt la locul lor.
Deci, în general, după iterații k prin matrice completă,
verificarea elementelor ultimele k este redundantă, deoarece știm
ei sunt în locația corectă deja.
>> Deci, dacă sunteți de sortare o serie de elemente n,
pe prima iterație - veti avea de a sorta toate elementele - primul n-0.
La doua repetare, va trebui să se uite la toate elementele, dar ultima -
prima n-1.
O alta optimizare ar putea fi pentru a verifica dacă lista este sortată deja
după fiecare iterație.
Dacă este deja sortate, nu avem nevoie pentru a face mai multe iteratii orice
prin listă.
Cum putem face acest lucru?
Ei bine, dacă nu vom face nici o swap pe un pass-through al listei,
e clar că lista a fost deja sortate, deoarece nu am nimic schimb.
Așa că nu avem cu siguranta pentru a sorta din nou.
>> Poate că ai putea inițializa o variabilă de pavilion numit "nu sortate" pentru a
falsă și schimba-l pe true dacă trebuie să schimbați orice elemente de pe
o iterație prin matrice.
Sau similar, fac un contor pentru a conta cât de multe swap faci
pe orice iterație dat.
La sfârșitul unei iterații, dacă nu schimbi oricare din elementele,
Știi lista este deja sortate și ați terminat.
Sortare bubble, la fel ca algoritmi de sortare alte, poate fi
optimizat pentru a lucra pentru orice elemente care au o metodă prin care se dispune.
>> Asta este, având în vedere două elemente ai un mod de a spune dacă prima
este mai mare, egală sau mai mică decât cea de a doua.
De exemplu, ai putea sorta litere ale alfabetului, spunând
că a <b, b <c, etc
Sau ai putea sorta zile ale săptămânii în care duminica este mai mică de luni
care este mai puțin decât marți.
>> Sortare bubble este în nici un caz un algoritm de sortare foarte eficient sau rapid.
Sa cel mai rau caz rulare este Big O de n ²
pentru că trebuie să facă iterații n printr-o listă
verificarea tuturor elementelor n fiecare trecere, NxN = n ².
Acest timp a alerga inseamna ca numarul de elemente ce te sortare crește,
timpul de functionare creste quadratically.
>> Dar dacă eficiența nu este o preocupare majoră a programului
sau dacă sunteți de sortare doar un număr mic de elemente,
s-ar putea găsi după Bubble util, deoarece
este unul dintre cele mai simple algoritmi de sortare pentru a înțelege
și pentru a coda.
Este, de asemenea, o modalitate foarte bună de a obține experiență cu traducerea unui teoretică
Algoritmul în codul funcționarea efectivă.
Ei bine, asta e după Bubble pentru tine. Multumesc pentru vizionare.
CS50.TV