[Powered by Google Translate] [Merge Sort] [Rob Bowden - Universitatea Harvard] [Acest lucru este CS50. - CS50.TV] Să vorbim despre un fel de îmbinare. Până acum ați văzut sortare cu bule, sortare inserție, și un fel de selecție. Deși voi un fel de val mâna mea la ceea ce vreau să spun cu mai bine, îmbinare de sortare, în general, se comportă mai bine decât oricare dintre aceste 3 tipuri. 

Dar, înainte de a vorbi despre un fel de îmbinare, hai sa vorbim despre fuzionarea 2 liste sortate. Vom numi procesul de luare a 2 liste sortate, cum ar fi acestea, și de a face o singură listă sortată de la ei - comasarea listele. Cum putem face acest lucru? Ei bine, o idee este să rămânem doar o listă pe finalul altă listă și apoi sortați lista de rezultate. 

În timp ce acest lucru functioneaza, e mult de lucru inutile. Putem să o facem mai repede decât doar de sortare. Observați că o idee greșită este de a lua doar cupe alternative din fiecare listă. Cu toate că poate părea că lucrările la prima, face acest lucru vom ajunge cu 4, 8, 15, 23, 16 - observați că 16 și 23 sunt din loc. Acest lucru se datorează faptului că 2 elemente care ar trebui să apară consecutiv în lista de îmbinat sunt în lista inițială aceeași. Atât 15 și 16 sunt în lista de pe partea stângă. Trucul este de a profita de faptul că ambele liste sunt deja sortate. Acest lucru înseamnă că, dacă ne uităm doar la primele elemente ale ambelor Lista de preturi - aici, 4 și 8 - una dintre ele trebuie să fie, de asemenea, primul element al listei rezultate din concentrare. Ei bine, de ce este asta? Ambele aceste liste sunt deja sortate, și așa mai departe, fie 4 sau 8 trebuie să fie mai mic element atunci când vom combina cele 2 liste. În acest caz, cel mai mic este de 4, astfel încât să putem scoate 4 și face primul element al listei noastre rezultate din concentrare. Acum vom continua fuziunea restul de 3 elemente ale prima listă și 4 elemente de doua listă. 

Încă o dată, avem nevoie doar să se uite la primul element al ambele liste. Mai mic de 2 trebuie să fie al doilea element al listei noastre rezultate din concentrare. De data aceasta, între 8 și 15 mai mic este de 8, și astfel vom introduce ca ca al doilea element al listei noastre sortate. Putem continua compararea primele elemente ale ambelor liste și eliminarea mai mic de 2. Compararea 15 și 23, 15 și este mai mic, astfel încât a noastră de al treilea element. Compararea acum 16 și 23, 16 este mai mică. Așa că e al patrulea element. 

Observați că 2 elemente venit de la aceeași listă într-un rând. Acesta este motivul pentru lista rezultată în urma concentrării nu poate doar elemente de supleanți din cele 2 liste. Compararea 50 și 23, 23 este mai mic, asa ca am ales asta. Între 50 și 42, 42 este mai mică. Între 50 și 108, 50 este mai mică. Și, în sfârșit, avem doar 108, așa că trebuie să meargă la sfarsitul listei noastre. Observați că avem o listă frumos, sortate. De fiecare dată când am comparat primele 2 elemente ale celor 2 liste noi am fost capabil de a determina urmatorul element al listei rezultate din concentrare. Acest lucru înseamnă că, în cazul în lista finală conține numere n, unde n este aici 8, atunci avem nevoie de cele mai multe comparații la n pentru a obține toate aceste numere în locul potrivit. O astfel de algoritm se spune pentru a rula în timp liniar, dar nu vă faceți griji despre asta aici. 

Folosind algoritmul nostru pentru fuzionarea, putem face un algoritm rapid de îmbinare de sortare. Deci, hai să resetați listele noastre. Există 2 pași mari în procesul de sortare de îmbinare. În primul rând, divizat continuu lista de cupe în jumatati până când vom avea o grămadă de liste cu doar 1 ceașcă în ele. Nu vă faceți griji în cazul în care o listă conține un număr impar si nu poti face o tăietură perfect curată între ele. Doar alege arbitrar, care să includă lista cupa suplimentar inch Deci, hai sa împărțit aceste liste. Acum avem 2 liste. Acum avem 4 liste. 

Și acum avem 8 Lista de preturi cu o singură ceașcă în fiecare listă. Deci asta e tot pentru pasul 1. Pentru pasul 2, ne uni în mod repetat perechi de liste utilizând algoritmul de îmbinare am învățat înainte. Fuzionarea 108 și 15, vom ajunge cu lista de 15, 108. Fuzionarea 50 și 4, vom ajunge cu 4, 50. Fuzionarea 8 și 42, vom ajunge cu 8, 42. Și fuzionează 23 și 16, vom ajunge cu 16, 23. Acum, toate listele noastre sunt de dimensiuni 2. Observați că fiecare dintre cele 4 liste este sortat. 

Astfel încât să putem începe fuzionarea perechi de liste din nou. Fuzionarea 15 și 108 și 4 și 50 - ia primul 4, apoi 15, apoi 50, apoi 108. Fuzionarea 8, 42 și 16, 23, vom lua prima 8, apoi 16, apoi 23, apoi 42. Deci, acum avem doar 2 liste de marimea 4, fiecare dintre care este sortat. Deci, acum am îmbina aceste două liste. În primul rând vom lua 4. Apoi luăm 8. Apoi luăm 15 și 16, apoi 23, apoi 42, apoi 50, apoi 108. Și am terminat. Avem acum o listă sortată. Deci, cât de repede a fost asta, mai exact? În termeni tehnici, sortare îmbinare este O (n log n), întrucât toate de sortare cu bule, sortare inserție, și un fel de selecție sunt O (n ²). De fapt, după cum veți afla în curând, nu va fi capabil de a veni cu un fel de care se comporta mai bine decat O (n log n) în cazul general. Din nou, nu vă faceți griji cu privire la această notație Big O, dacă nu l-ați văzut încă. 

Doar știu că acest lucru înseamnă, dacă ne-am dorit pentru a sorta o listă foarte mare sortare sortare cu bule, sortare inserție, și de selecție ar putea avea potential semnificativ mai mare decât îmbinare de sortare. Aceasta nu înseamnă că un fel de îmbinare va fi mai rapidă pentru toate listele de sau chiar pentru orice listă unică sub un anumită dimensiune. De exemplu, ar putea fi un fel inserție mai rapidă de sortare pentru toate listele de mai mici decat 5 elemente. În practică, un fel de îmbinare este de obicei mai rapid pentru Lista de preturi la fel de mici ca 50 de elemente. 

Dar aceasta viteza in plus nu vine fără un preț. Spre deosebire de felul de alte noastre, care să ia o listă și să modifice lista de la locul de până când vom obține o listă sortată, sortare îmbinare are nevoie de unele spațiu suplimentar să fuzioneze 2 liste împreună. Noi nu putem folosi imediat listele care sunt îmbinate pentru a stoca lista rezultată în urma concentrării din moment ce s-ar putea înlocui elementele care încă trebuie să fie îmbinate. Acest spațiu este un pic de un preț, dar, de obicei, nu este nerezonabil. Și asta e tot un fel de îmbinare. 

Numele meu este Rob Bowden, iar acest lucru este CS50. [CS50.TV] - Sortare și selecție. [Râde] Oh, trebuie să iau asta prea pentru că am schimbat modul în care am fost o prezenta. Lista din partea stângă. Asta a fost o greseala de tipar. [Misspoke] Am dat-on bară - [Râde] Nu știu ce -