[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