>> [MUSIC PLAYING]
>> DOUG LLOYD: OK, belə ki, bir birləşməsi sort başqa bir alqoritm edir
biz həyata düzmək üçün istifadə edə bilərsiniz ki, bir sıra elementləri.
Biz görəcəksiniz kimi, bu var ki, bir çox fundamental fərq
seçim sort, bubble sort və durub sırala
ki, həqiqətən, olduqca ağıllı olun.
>> birləşməsi əsas ideyası sort kiçik serialların düzmək üçün
və həmin Diziler birləşdirmək birlikdə və ya Odur birləşməsi
səbəbdən sıralanır üçün konseptual mənada adı.
sort yoxdur birləşməsi yolu bu bir alət istifadə edərək, var
nə olan recursion adlı Biz tezliklə söhbət etmək olacaq
lakin biz, həqiqətən hələ söhbət yoxdur.
>> Burada birləşməsi sırala əsas fikirdir.
Serialın sol yarım sırala n fərz 1-dən böyükdür.
Mən deyəndə nə demək n fərz 1 böyükdür
Mən biz razı edə bilər ki, bir sıra əgər yalnız bir element ibarətdir,
sıralanır.
Biz, həqiqətən, ehtiyac yoxdur bu bir şey etmək.
Biz yalnız sıralanır elan edə bilər.
Bu, yalnız bir element var.
>> Belə pseudocode, təkrar edir serialın sol yarım sort
sonra sağ yarım array sort, sonra birlikdə iki yarıya indirir daxil.
İndi artıq ola bilər düşünür, bu cür yalnız
the-- Siz off qoyulması etdiyiniz kimi səslənir Siz, həqiqətən, heç bir şey məşğul deyilik.
Siz sol sort deyərək edirik yarım, sağ yarım sort,
lakin izah deyilik Mənə necə bunu edirik.
>> Amma uzun kimi xatırlayıram bir sıra bir element deyil,
biz sıralanır elan edə bilər.
Sonra biz yalnız birlikdə onları birləşdirə bilər.
Və həqiqətən Birləşmə sort arxasında əsas ideyası,
ki, bunu qırmaq üçün Sizin seriallarda ölçüsü biri var.
Və sonra oradan bərpa.
>> Sort mütləq deyil Birleştirme mürəkkəb alqoritm.
Və bu da bir az var görüntüləmək üçün mürəkkəb.
Beləliklə, ümid edirəm, vizual ki, mən siz boyunca təqib kömək edəcək burada var.
Mən hər şeyi rəvayət mənim ən yaxşı çalışacağıq və bu bir az daha vasitəsilə davam
yavaş-yavaş digər olanları daha yalnız inşallah baş almaq üçün
Birləşmə sort ideya ətrafında.
>> Beləliklə, biz eyni array var digər çeşidlənməsi alqoritm videos
Siz gördüm əgər Odur altı element array.
Və burada pseudocode kodu sortudur sol yarısı, sağ yarım sort,
birlikdə iki yarıya indirir daxil.
Belə ki, bu çox qaranlıq kərpic qırmızı götürək array və bu sol yarım sort.
>> Hazırda Belə ki, biz gedirik sağ məhsulları ignore.
Bu var, lakin biz istəyirik hələ ki, bir addım da.
Biz heç sort Serialın sağ yarım.
Biz növ sol istəyirik serialın yarısı.
Və yalnız naminə bir az daha olan
aydın, mən müraciət edə bilərsiniz nə addım biz istəyirik,
Mən keçid gedirəm narıncı bu dəsti rəng.
İndi, biz hələ söhbət edirik orijinal sıra eyni sol yarısı.
Amma edə ki, ümid edirəm müxtəlif maddələr rəngləri baxın,
bu bir az daha etmək lazımdır burada neler təmizləmək.
>> OK, belə ki, indi biz bir üç element array.
Bu sol yarım sort necə hələ bu addım array?
Biz sol düzmək üçün çalışdığınız kərpic qırmızı serialın yarısı
sol yarısı olan İndi narıncı rəngli etdik.
>> Yaxşı, biz cəhd və bilər yenə bu prosesi təkrar edin.
Belə ki, biz hələ də istəyirik düzmək üçün çalışır orta
tam array sol yarısı.
sol yarısı array, mən yalnız gedirəm
özbaşına qərar ki, sol yarım sağ yarım daha kiçik olacaq,
bu olur, çünki üç elementdən ibarətdir.
>> Və mən ki, gedirəm sol yarım array sol yarısı
yalnız element beş edir.
Beş, bir element olan array, biz bu sort üçün necə.
Və belə beş çeşidlənir.
Biz yalnız bəyan olacaq.
Bu bir element array var.
>> Beləliklə, biz indi sıralaması etdik sol half-- sol yarısı
daha doğrusu, biz sıralanır etdik portağal sol yarısı.
Belə ki, indi üçün hələ tam ümumi serialın sol yarım,
biz sağ yarım düzmək lazımdır portağal, və ya bu məhsulları.
Biz bunu necə edə bilərəm?
Bəli, biz iki element array var.
Beləliklə, biz sol yarım sort bilər iki serialın edir.
Iki bir elementidir.
Belə ki, ismarıcları sıralanır. Sonra biz sağ yarım sıralayabilirsiniz
array, bir hissəsinin.
Bu default sort var.
>> Bu artıq ilk dəfə bir birləşməsi addım əldə etdik.
Biz, baxmayaraq ki, başa biz indi cür aldadan iç içə edirik
ki, çətin sort var recursion ilə şey,
Siz, Sizin saxlamaq lazımdır Biz harada rəhbərlik.
Beləliklə, biz sol sort var narıncı hissəsinin yarısı.
>> İndi, biz çeşidlənməsi ortasında istəyirik narıncı hissəsinin sağ yarım.
Və prosesi, biz addım olmaq indi,
birlikdə iki yarıya indirir daxil.
Biz iki yarıya indirir baxdığımızda serialın biz iki və bir baxın.
Hansı element kiçik?
Biri.
>> Sonra hansı element kiçik?
Bəli, bu, iki və ya bir şey var.
Belə ki, iki deyil.
Belə ki, indi yalnız yenidən nizama salmaq üçün Biz kontekstində olduğu,
biz bilmişik portağal sol yarısı
və mənşə sağ yarım.
Mən rəng dəyişdi etdik bilirik biz harada yenidən, lakin var.
Və səbəbi bu idi Bu proses, çünki
aşağı iterating, davam etmək niyyətindədir.
Biz sol sıralaması etdik keçmiş portağal yarım
və keçmiş portağal sağ yarım.
>> İndi biz bu daxil etmək lazımdır birlikdə çox iki yarıya indirir.
Yəni biz istəyirik addımdır.
Beləliklə, biz bütün hesab İndi yaşıl elementlər,
Orijinal serialın sol yarım.
Və biz bu birləşməsi eyni proses istifadə edərək,
biz iki birləşməsi üçün etdi və bir yalnız bir an əvvəl.
>> sol yarısı, kiçik sol yarısında element beş edir.
kiçik element haqqında sağ yarım biridir.
O hansı kiçik?
Biri.
>> kiçik element haqqında sol yarısı beş edir.
kiçik element haqqında sağ yarım iki.
Kiçik nədir?
Iki.
Və sonra nəhayət beş heç bir şey, biz beş demək olar.
>> OK, belə ki, böyük şəkil, edək ikinci bir fasilə etmək
Biz harada və anlamaq.
Biz açılmış əgər əvvəldən, biz
İndi başa ümumi array yalnız
burada pseudocode kodu bir addım.
Biz bilmişik Serialın sol yarısı.
>> Orijinal Xatırladaq ki, order beş, iki, biri idi.
Bu prosesi ilə və aşağı quş balası və təkrar,
problem qırmaq davam aşağı kiçik və kiçik hissəyə,
biz indi başa pseudocode bir addım
bütün başlanğıc array üçün.
Biz sol yarım bilmişik.
>> Belə ki, indi orada dondurmaq bildirin.
İndi hüququnu sort imkan Orijinal serialın yarısı.
Və biz bunu olacaq Eyni iterativ keçir
şeyi parçalayaraq prosesi və sonra onları birlikdə birləşməsi.
>> Belə ki, sol yarısı qırmızı, və ya sol yarım
orijinal sağ yarısı array, mən demək gedirəm üç edir.
Yenə burada ardıcıl olan alıram.
Bir tək varsa elementlərin sayı, onu
həqiqətən olub etməz Siz sol, bir kiçik etmək
və ya doğru bir kiçik.
>> Hansı məsələ zaman sizə ki, aparılması bu problem
bir birləşməsi, siz ardıcıl olmaq lazımdır.
Siz ya həmişə lazımdır sol yan kiçik etmək
və ya həmişə etmək lazımdır sağ kiçik.
Burada həmişə seçdiyiniz sol tərəfində kiçik etmək
zaman mənim array, və ya mənim sub-array, bir tək ölçüsü edir.
>> Üç bir element, və buna çeşidlənir.
Biz ehtimalı leveraged sonra Bizim bütün proses boyu bu günə qədər.
Belə ki, indi hüququ sort imkan sağ yarım yarısı,
və ya qırmızı sağ yarım.
>> Yenə bu aşağı split lazımdır.
Bu bir element array deyil.
Biz sıralanır elan edə bilməz.
Və belə ki, ilk, gedirik sol yarım sort.
>> sol yarısı bir element, belə ki, ismarıcları sort var.
Sonra sağ sort olacaq bir element yarım.
Bu ismarıcları sıralanır. Və indi, Biz birlikdə bu iki daxil edə bilərsiniz.
Dörd kiçik və sonra altı kiçik.
>> Yenə biz bu nöqtədə etdik?
Biz sol sıralaması etdik sağ yarısı yarısı.
Və ya orijinal geri gedir var idi rəng,
biz sol sıralaması etdik yumşaq qırmızı yarısı.
Bu, ilk qaranlıq kərpic idi qırmızı və indi daha yumşaq qırmızı,
və ya bir yumşaq qırmızı idi.
>> Və sonra biz sıralanır etdik yumşaq qırmızı sağ yarım.
İndi də, onlar yalnız yenidən yaşıl istəyirik Biz prosesi olacaq, çünki.
Və biz təkrar var Bu üzərində.
>> Belə ki, indi biz bu daxil edə bilərsiniz birlikdə iki yarıya indirir.
Və biz burada nə var.
Qara xətt Belə ki, yalnız sol yarım bölünür
və bu cür hissəsinin sağ yarım.
>> Biz kiçik dəyəri müqayisə serialın sol tərəfində
və ya pardon, kiçik yarıda buraxdı dəyəri
hüququnun kiçik dəyəri yarım və üç kiçik olduğunu tapmaq.
İndi bir optimallaşdırılması bir az, sağ?
Heç bir şey həqiqətən var sol tərəfində ayrıldı.
>> Qalan bir şey yoxdur sol tərəfində,
belə ki, biz səmərəli edə bilərsiniz yalnız biz elan edə bilər move--
Bunun qalan əslində çeşidlənir və yalnız tack
heç bir şey yoxdur, çünki, qarşı müqayisə üçün başqa.
Və biz bilirik sağ ki, Sağ çeşidlənir.
>> OK, belə ki, indi yenidən dondurmaq imkan və Biz hekayə harada şekillendirmek.
Ümumi array, biz nə həyata var?
Biz, həqiqətən, yerinə yetirmək etdik indi bir addım iki addımlar.
Biz sol yarım sıralanır, və biz sağ yarım sıralanır.
>> Belə ki, indi qalır ki, bütün bizim üçün birlikdə bu iki yarıya indirir daxil etmək üçün.
Beləliklə, biz ən aşağı qiymətli müqayisə serialın hər yarım element
və öz növbəsində davam etdirilir.
Üç azdır, belə ki, bir gedir.
>> İki üç azdır, belə ki, iki gedir.
Üç 5-dən az, belə ki, üç gedir.
Dörd 5-dən az, belə ki, dörd gedir.
Sonra beş, altı azdır və altı bütün qalır.
>> İndi mən bilirəm ki, addımlar bir çox idi.
Və biz bir çox tərk etdik Bizim sonra yaddaş.
Və o boz meydanların nə var.
Ki, etdi kimi və yəqin ki, hiss durub sırala artıq çox, bubble
sort, və ya seçim sort.
>> Amma əslində, çünki Bu proseslərin çox
Eyni sýrada da olur ki, yenə biz lazımdır bir şey deyil
Biz haqqında danışmaq zaman haqqında danışmaq gələcəkdə recursion video--
həqiqətən bu alqoritm aydın əsaslı deyil
bir şey daha fərqli biz əvvəl gördük
lakin əhəmiyyətli dərəcədə də daha səmərəli.
>> Niyə ki?
Yaxşı, pis ssenari, biz
n elementləri split və sonra onları recombine.
Amma biz recombine zaman Onlara nə edirik
əsasən iki qatına çıxarır kiçik seriallarda ölçüsü.
Biz bir element bir dəstə var Diziler ki, biz səmərəli
iki element serialların daxil birləşdirir.
Və sonra biz bu almaq iki element Diziler
və onları birlikdə birləşdirmək belə dörd element Diziler, və,
və s, və s, biz qədər bir n element array var.
>> Amma necə bir çox doublings Bu n almaq lazımdır?
Geri telefon kitab misal düşünün.
Neçə dəfə biz qoparmaq var yarısında telefon kitab, necə daha çox
dəfə biz telefon kitab qoparmaq var yarısında, əgər telefon kitab ölçüsü
iki dəfə?
Yalnız bir doğru var?
>> Belə ki, bir növ var burada logarithmic element.
Amma biz də hələ ən azı n elementləri bütün baxmaq.
, Ən pis halda belə sort n log n çalışır birləşməsi.
Biz baxmaq lazımdır n elementləri bütün,
və biz onları birləşdirmək lazımdır birlikdə log n addımlar dəstləri.
Ən yaxşı ssenari, array mükəmməl çeşidlənir.
Bu əladır.
Amma alqoritm əsasında biz burada var biz hələ split və recombine lazımdır.
Bu halda olsa da, recombining təsirsiz növüdür.
Bu lazım deyil.
Amma biz hələ keçmək hər halda bütün proses.
>> Ən yaxşı halda belə və ən pis halda,
bu alqoritm n log n vaxt çalışır.
Sort Birleştirme mütləq bir az trickier edir digər əsas çeşidlənməsi alqoritmlərin çox
biz CS50 haqqında söhbət ancaq etdik əhəmiyyətli dərəcədə daha güclü.
>> Və əgər heç tapmaq münasibətilə onu lazımdır
və ya düzmək üçün istifadə etmək böyük data set əldə
recursion ideyası ətrafında baş həqiqətən güclü olacaq.
Və bu etmək olacaq sizin proqramları həqiqətən daha səmərəli
başqa bir şey qarşı sort daxil istifadə edərək.
Mən Doug Lloyd edirəm.
Bu CS50 edir.