[MÜZİK OYUN] 

Doug LLOYD: Tamam, bir birleştirme Sıralama başka algoritma Biz dışarı sıralamak için kullanabileceğiniz Bir dizinin elemanları. Biz göreceğiz Ancak, bu var bir Çok temel fark Seçim sıralama, kabarcık sıralama ve yerleştirme sıralama o gerçekten çok zeki olun. 

Birleştirme arkasındaki temel fikir Sıralama küçük diziler sıralamak için ve daha sonra bu dizileri birleştirmek Birlikte veya them-- birleştirme dolayısıyla sıralı sırayla aşkına--. Sıralama yapar birleştirme yolu Bu bir araç yararlanarak gereğidir ne olduğu, yineleme denilen Biz yakında bahsediyoruz gidiyoruz ama biz gerçekten hakkında henüz konuşmadık. 

İşte birleştirme sıralama ardındaki temel fikir. Dizinin sol yarısını sıralama n varsayılarak 1 daha büyüktür. Ve ben derken ne demek n varsayılarak, 1 daha büyüktür Sanırım kabul düşünüyorum olduğu bir dizi halinde yalnızca tek bir elemandan oluşur, o tür var. Biz aslında ihtiyacımız yok buna bir şey yapmak için. Biz sadece sıralanabilir için ilan edebilir. Sadece bir tek eleman var. 

Yani sözde kod, yine, dizinin sol yarısını sıralamak sonra sağ yarım dizi sıralamak, sonra birlikte iki yarısı birleştirme. Şimdi, zaten olabilir düşünme, bu tür sadece Şeyin kapalı koyarak konum gibi geliyor aslında hiçbir şey yapmıyorsun. Sen sol sıralamak söylüyorsun yarısı sağ yarısı sıralamak ama sen söylemediğin Bana bunu nasıl yapıyorsun. 

Ama sürece unutmayın Bir dizi tek unsurdur, Biz o tür bildirebilirsiniz. Sonra biz sadece onları bir arada birleştirebilirsiniz. Ve bu aslında Birleştirme sıralama ardındaki temel fikir, Bu yüzden yıkmak olduğunu senin diziler büyüklüğü biri vardır. Ve sonra oradan yeniden. 

Sıralama kesinlikle Birleştirme Karmaşık bir algoritma. Ve o da biraz var görselleştirmek için karmaşık. Yani umarım, görselleştirme ben Eğer birlikte takip yardımcı olacaktır burada var. Ve ben bir şeyler anlatmaya elimden geleni yapacağım ve bu biraz daha ile devam Yavaş yavaş diğer olanlardan daha Sadece umarım başını almak için Birleştirme tür arkasındaki fikir etrafında. 

Yani biz aynı dizi var Diğer sıralama algoritması videoları Gördüğünüz eğer them-- altı unsur dizisi. Ve burada bizim pseudocode kodu tür Sol yarısı sağ yarısı sıralamak Birlikte iki yarısını birleştirmek. Yani bu çok karanlık bir tuğla kırmızı atalım Dizi ve bunun sol yarısı sıralayın. 

Bu yüzden şu anda, biz gidiyoruz Sağdaki şeyler görmezden. Orada, ama biz konum henüz o aşamada. Biz değiliz de sıralama Dizinin sağ yarısı. Biz tür sol konum Dizinin yarısı. Ve sadece uğruna biraz daha olmak açık, bu yüzden başvurabilirsiniz Ne adım biz konum, Ben geçmek için gidiyorum turuncu, bu setin rengi. Şimdi, biz hala hakkında konuşuyor Orijinal dizinin aynı sol yarısı. Ama edememek tarafından umuyorum çeşitli öğelerin renklerine bakın o biraz daha yapacağız Burada neler oluyor temizleyin. 

Tamam, şimdi biz bir Üç element dizisi. Biz bu sol yarısını sıralama nasıl hala bu adım dizi? Biz sol sıralamak için çalışıyoruz tuğla kırmızısı array-- yarısı Sol yarısı Ben şimdi turuncu renkli ettik. 

Eh, biz denemek olabilir ve Yine bu işlemi tekrarlayın. Yani biz hâlâ sıralamak için çalışıyor orta Tam dizinin sol yarısı. Sol yarısı Dizi, ben sadece gidiyorum keyfi karar olduğunu sol yarım Sağ yarısından daha küçük olacak, Bu olur çünkü Üç öğeden oluşur. 

Ve bu yüzden söylemek için gidiyorum Sol yarısı dizisi sol yarısı Sadece eleman beş. Beş, tek bir eleman olmak Dizi, biz bunu sıralamak için biliyorum. Ve böylece beş sıralanır. Biz sadece beyan edeceğiz. Tek eleman dizisi var. 

Yani biz şimdi sıralanmış ettik Sol half-- sol yarısı ya da daha doğrusu, biz kriteri ettik turuncu sol yarısı. Yani şimdi, sırayla hala tam Genel dizinin sol yarısı, Doğru yarısını sıralamak gerekiyor turuncu veya bu şeyler. Biz nasıl yapacağız? Peki, biz bir iki eleman dizi var. Bu yüzden sol yarısını sıralayabilirsiniz iki dizisinin. İki tek unsurdur. Yani varsayılan sıralama kriteri oluyor. Sonra sağ yarısını sıralayabilirsiniz tadını birinin bu kısmının. Bu varsayılan çeşit var. 

Bu şimdi ilk kez Biz bir birleştirme adımı ulaştınız. Biz her ne kadar, tamamlamış Şimdi biraz down-- iç içe konum ve bu zor bir çeşit yineleme ile bir şey, Eğer sizin yanınızdaki tutmak gerekir Nerede ilgili baş. Bu yüzden sol çeşit var Turuncu bölümünün yarısı. 

Ve şimdi, biz sıralama ortasýndayýz Turuncu bölümünün sağ yarısı. Ve bu süreçte, biz adım olması şimdi hakkında Birlikte iki yarısını birleştirmek. Biz iki yarısı baktığımızda dizinin, biz iki ve bir bakın. Hangi element küçüktür? Bir. 

Daha sonra bu eleman daha küçüktür? Peki, iki ya da hiçbir şey. Yani iki. Yani şimdi, sadece tekrar çerçeve Biz bağlamında nerede, biz sıralamış turuncu sol yarısı ve menşe sağ yarısı. Ben renkleri değişti biliyorum nerede kalmıştık yine, ama bu. Ve neden ben yaptım bu işlem olduğu için olan Aşağı yineleme, devam edecek. Biz sol kriteri ettik Eski portakal yarısı ve eski portakal sağ yarısı. 

Şimdi, biz o birleştirmek gerekiyor birbirine çok iki yarısı. Yani biz konum adımdır. Bu yüzden bütün düşünün Şimdi yeşil unsurlar, Orijinal dizinin sol yarısı. Ve biz o birleştirme Aynı işlem kullanılarak biz iki birleştirmek için yaptım ve bir sadece bir an önce. 

Sol yarım, en küçük Sol yarısında eleman beştir. En küçük eleman üzerinde Sağ yarım biridir. Bunların hangisi daha küçüktür? Bir. 

En küçük eleman üzerinde Sol yarım beş. En küçük eleman üzerinde Sağ yarım ikidir. En küçük nedir? İki. Ve son olarak beş hiçbir şey biz beş söyleyebiliriz. 

Tamam, büyük resim, diyelim Bir saniye bir mola Nerede olduğumuzu ve anlamaya. Biz kimden başladıysanız başından, biz şimdi tamamlamış Genel dizi sadece Burada pseudocode kodunun bir adım. Biz sıralamış Dizinin sol yarısı. 

Orijinal hatırlayın Sipariş beş, iki, bir oldu. Bu süreçten geçiyor tarafından aşağı yuvalama ve yinelenen, Sorunu kırmaya devam Aşağı küçük ve daha küçük parçalar haline, Şimdi tamamlamış pseudocode birini adım Tüm başlangıç ​​dizisi için. Biz onun sol yarısı sıralamış. 

Yani şimdi orada dondurma edelim. Ve şimdi hakkını sıralamak edelim Orijinal dizinin yarısı. Ve biz tarafından o yapacağız Aynı yinelemeli geçiyor şeyleri aşağı kırılma süreci ve daha sonra onları bir arada birleştirilmesi. 

Yani sol yarısı kırmızı veya sol yarım orijinal sağ yarısı Dizi, söylemek için gidiyorum üçtür. Yine, ben burada tutarlı olmaya çalışıyorum. Eğer bir garip varsa elemanların sayısı, o Gerçekten farketmez Eğer sol bir küçük yapmak ya da doğru bir küçük. 

Önemli olan zaman sizi o yürütürken bu sorunla karşılaştığınızda Bir birleştirme, tutarlı olması gerekir. Ya hep gerekir Bir sol taraf daha küçük yapmak ya da her zaman yapmak gerekir sağ tarafı daha küçük. Burada, ben her zaman seçtiniz sol taraf daha küçük yapmak benim dizi veya benim alt dizi, garip bir boyutudur. 

Üç tek unsurdur, ve bu yüzden sıralanır. Biz bu varsayımı kaldıraçlı ettik bizim tüm süreç boyunca şimdiye kadar. Yani şimdi hakkını sıralamak edelim sağ yarısında yarısı, ya da kırmızı sağ yarısı. 

Yine, biz bu aşağı bölmek gerekir. Bu, tek bir unsur dizisi değil. Biz o tür beyan edemez. Ve böylece ilk, biz gidiyoruz sol yarısı sıralamak için. 

Sol yarım, tek bir unsurdur, yani varsayılan olarak çeşit var. Sonra sağa sıralamak için gidiyoruz Tek bir öğedir yarısı. Varsayılan sıralama kriteri oluyor. Ve şimdi, Beraber bu ikisini birleştirebilirsiniz. Dört küçük ve Daha sonra altı küçüktür. 

Yine, ne bu noktada yapmış? Biz sol kriteri ettik Sağ yarım yarım. Ya da orijinal geri dönüyor vardı renkler, Biz sol kriteri ettik yumuşak kırmızı yarısı. Başlangıçta koyu tuğla oldu Kırmızı ve şimdi yumuşak bir kırmızı var, ya da bir yumuşak kırmızı oldu. 

Ve sonra biz kriteri ettik yumuşak kırmızı sağ yarısı. Şimdi de, onlar sadece, yine yeşil konum Biz bir süreçten geçiyoruz çünkü. Ve biz tekrarlamak zorunda Bu tekrar ve tekrar. 

Yani şimdi o birleştirebilirsiniz Birlikte iki yarısı. Ve biz burada ne var. Siyah çizgi Yani sadece Sol ikiye bölünür ve bu tür kısmının sağ yarısı. 

Biz en küçük değeri karşılaştırmak array-- sol tarafındaki ya afedersiniz, küçük Sol yarısı değeri Sağ en küçük değere Yarım ve üç küçük olduğunu bulmak. Ve şimdi bir optimizasyon biraz, değil mi? Hiçbir şey gerçekte var Sol tarafta bıraktı. 

Kalan bir şey yok sol tarafta, bu yüzden verimli olabilir sadece biz ilan edebilir move-- Gerisi aslında sıralanır ve sadece tack hiçbir şey yok, çünkü üzerinde karşılaştırmak için başka. Ve biz biliyoruz sağ tarafı sağ tarafında sıralanır. 

Tamam, şimdi tekrar donmasına izin ve Biz hikayenin neresinde olduğunu anlamaya. Genel dizide, ne başardık? Biz aslında başarmak ettik şimdi bir adım ve iki adımları tekrarlayın. Biz sol yarısı sıralanır ve Doğru yarısını sıralanır. 

Yani şimdi, kaldığı hepimizin için birlikte bu iki yarısını birleştirmek için. Bu yüzden en değerli karşılaştırmak Dizinin her yarım elemanının ve sırayla devam edin. Bir üç daha azdır, böylece bir gider. 

İki, üç daha azdır, bu nedenle iki gider. Üç 5 den az, Yani üç gider. Dört 5 den az,, dört gider. Sonra beş, altı daha azdır ve altı tüm kalır olduğunu. 

Şimdi, biliyorum, o adımları çok oldu. Ve biz çok bıraktık Bizim sonrasında bellek. Ve o gri kareler ne olduğunu. Bu aldı gibi Ve muhtemelen keçe Ekleme sıralama daha uzun lot, kabarcık sıralama veya seçim sıralama. 

Ama aslında, çünkü Bu işlemlerin çok Aynı olan Zamanın de gerçekleşiyor hangi yine yaparız şeydir biz hakkında konuşmak ne zaman hakkında konuşmak gelecekteki bir yineleme video-- aslında bu algoritma açıkça temelde bir şey daha farklı Daha önce gördüğümüz ancak önemli ölçüde aynı zamanda daha verimli. 

Neden? Peki, en kötü senaryo, biz n unsurları bölmek ve sonra onları recombine. Ama biz recombine zaman Onları, ne yapıyoruz temelde ikiye katlanıyor Daha küçük dizilerin boyutu. Biz bir elemanın bir grup var diziler biz etkin bir şekilde İki eleman diziler halinde birleştirir. Ve sonra biz o almak İki element diziler ve içine birleştirebilirsiniz böylece dört elemanlı bir dizi, ve ve böylece, ve böylece, biz gelene kadar Tek n eleman dizi var. 

Ama kaç çiftlenmeler o n almak için sürer? Geri telefon rehberi örnek düşünün. Kaç kere biz gözyaşı var yarısında telefon rehberi, daha kaç kere telefon rehberini gözyaşı var yarısında, eğer telefon rehberinin boyutu iki katına? Sadece bir sağ, yok mu? 

Yani bir çeşit var Burada logaritmik unsur. Ama biz de hala var en azından n tüm öğeleri bak. , En kötü durum senaryosunda Yani sıralama n günlük n çalışır birleştirme. Biz bakmak zorunda n bütün elemanları, ve biz onları birleştirmek zorunda Birlikte günlük n adımlar setleri. En iyi senaryoya göre, Dizi mükemmel sıralanır. Bu harika. Ama algoritmasına dayanan Biz burada var biz hala bölünmüş ve rekombinasyona var. Bu durumda da, yeniden birleştirici etkisiz türüdür. Bu gerekli değildir. Ama biz yine de geçmesi Zaten bütün süreç. 

En iyi durumda Yani ve en kötü durumda, Bu algoritma n günlüğüne n zaman içinde çalışır. Birleştirmeli sıralama kesinlikle biraz daha zordur Diğer ana sıralama algoritmaları daha Biz CS50 hakkında konuştuk ama ettik önemli ölçüde daha güçlü. 

Ve eğer öyleyse hiç bulmak vesilesiyle ihtiyaç için veya sıralamak için kullanmak Büyük veri seti, alıyorum özyineleme fikri etrafında başınızı gerçekten güçlü olacak. Ve bunu yapmak için gidiyor senin programlar gerçekten çok daha etkili başka bir şey karşı birleştirmeli sıralama kullanarak. Ben Doug Lloyd değilim. Bu CS50 olduğunu.