[მუსიკის დაკვრა] 

DOUG LLOYD: OK, ასე შერწყმა დალაგების არის კიდევ ერთი ალგორითმი რომ ჩვენ შეგვიძლია გამოვიყენოთ დასალაგებლად out ელემენტების მასივი. მაგრამ, როგორც ვნახავთ, ის მივიღე ძალიან ფუნდამენტური განსხვავება საწყისი შერჩევის დალაგების, bubble დალაგების, და Insertion დალაგების რომ ეს მართლაც საკმაოდ ჭკვიანი. 

ძირითადი იდეა უკან შერწყმა დალაგების დასალაგებლად პატარა კოლექტორები და შემდეგ გავაერთიანებთ იმ მასივების ერთად, ან შერწყმა them-- აქედან გამომდინარე, name-- დახარისხებული მიზნით. ისე, რომ შერწყმა დალაგების აკეთებს ეს არის ოპერაციული ინსტრუმენტი მოუწოდა უკან, რაც ჩვენ ვაპირებთ უნდა ლაპარაკი მალე, მაგრამ ჩვენ ნამდვილად არ ისაუბრა არავის გაუკეთებია. 

აი ძირითადი იდეა უკან შერწყმა დალაგების. Sort მარცხენა ნახევარში მასივი, თუ, რა თქმა n მეტია 1. და რას ვგულისხმობ, როცა ვამბობ, თუ, რა თქმა n მეტია 1, მე ვფიქრობ, შევთანხმდებით, რომ, თუ მასივი მხოლოდ შედგება ერთი ელემენტი, ეს დახარისხებული. ჩვენ რეალურად არ უნდა არაფრის გაკეთება მას. ჩვენ შეგვიძლია მხოლოდ განაცხადოს, უნდა იყოს დახარისხებული. ეს მხოლოდ ერთ ელემენტს. 

ასე რომ, pseudocode, კიდევ ერთხელ, დასალაგებლად მარცხენა ნახევარში მასივი, მაშინ დასალაგებლად მარჯვენა ნახევარში მასივი, შემდეგ შერწყმა ორი halves ერთად. ახლა უკვე თქვენ შეიძლება იყოს ფიქრობს, რომ ეს ერთგვარი მხოლოდ ჟღერს თქვენ აყენებს off the-- თქვენ არ რეალურად აკეთებს არაფერს. თქვენ ამბობთ, რომ დასალაგებლად მარცხენა ნახევარში, დასალაგებლად მარჯვენა ნახევარში, მაგრამ თქვენ არ ვეუბნებით ჩემთვის, როგორ გამოგდის. 

მაგრამ გახსოვდეთ, რომ მანამ, სანამ მასივი ერთ ელემენტს, ჩვენ შეგვიძლია განვაცხადოთ, რომ ეს დახარისხებული. შემდეგ ჩვენ შეგვიძლია მხოლოდ აერთიანებს მათ ერთად. და ეს არის რეალურად ძირითადი იდეა უკან შერწყმა დალაგების, არის შესვენება მას ისე, რომ თქვენი კოლექტორები არის ზომა ერთი. და მაშინ აღვადგინოთ იქ. 

შერწყმა დალაგების არის ნამდვილად რთული ალგორითმი. და ეს არის ასევე პატარა რთული ვიზუალურად. ასე რომ, იმედია, ვიზუალიზაცია, რომ მე აქ დაგეხმარებათ დაიცვას გასწვრივ. და ვეცდები ჩემი საუკეთესო ჰყვებოდა რამ და გაგრძელება მეშვეობით ამ ცოტა მეტი ნელა, ვიდრე სხვა პირობა მხოლოდ იმიტომ, რომ იმედია, თქვენი უფროსი გარშემო იდეები უკან შერწყმა დალაგების. 

ასე რომ, ჩვენ იგივე მასივი, როგორც სხვა დახარისხება ალგორითმი ვიდეოები თუ ვნახე them-- ექვსი ელემენტს მასივი. ჩვენი pseudocode კოდი აქ არის ერთგვარი მარცხენა ნახევარში, დასალაგებლად მარჯვენა ნახევარში, შერწყმა ორი halves ერთად. ასე რომ, მოდით ეს ძალიან მუქი წითელი აგურის array და დასალაგებლად მარცხენა ნახევარი. 

ასე რომ, ამ დროისათვის, ჩვენ ვაპირებთ იგნორირება პერსონალის უფლება. ის არსებობს, მაგრამ ჩვენ არა, რომ ნაბიჯი არ არის. ჩვენ არ ვართ დალაგების მარჯვენა ნახევარში მასივი. ჩვენ ვართ ერთგვარი მარცხენა ნახევარში მასივი. და მხოლოდ გულისთვის მიმდინარეობს ცოტა მეტი ნათელია, ასე რომ შემიძლია ეხება რა ნაბიჯი ჩვენ შესახებ, მე ვაპირებ გადართოთ ფერი ეს ნაკრები ფორთოხალი. ახლა, ჩვენ ჯერ კიდევ ვსაუბრობთ იგივე მარცხენა ნახევარში ორიგინალური მასივი. მაგრამ მე იმ იმედით, რომ დგომით შეუძლია ეხება ფერები სხვადასხვა ნივთები, ის, რომ მას ცოტა მეტი გარკვევა, თუ რა ხდება აქ. 

OK, ასე რომ, ახლა ჩვენ გვაქვს სამი ელემენტს მასივი. როგორ უნდა დაალაგოთ მარცხენა ნახევარში მასივი, რომელიც ჯერ კიდევ ეს ნაბიჯი? ჩვენ ვცდილობთ, რომ დასალაგებლად მარცხენა ნახევარი წითელი აგურის მასივი მარცხენა ნახევარში, რომელიც მე ახლა ფერადი ფორთოხალი. 

ისე, ჩვენ შეგვიძლია ვცადოთ და ვიმეორებ ეს პროცესი კიდევ ერთხელ. ასე რომ, ჩვენ ჯერ კიდევ შუა ცდილობს დასალაგებლად მარცხენა ნახევარში სრული მასივი. მარცხენა ნახევარში მასივი, მე უბრალოდ აპირებს თვითნებურად გადაწყვიტოს, რომ მარცხენა ნახევარში იქნება ნაკლები მარჯვენა ნახევარში, იმიტომ, რომ ეს მოხდება შედგება სამი ელემენტისაგან. 

ასე რომ, მე ვაპირებ ვთქვა, რომ მარცხენა ნახევარში მარცხენა ნახევარში მასივი მხოლოდ ელემენტს ხუთ. ხუთი, რომ არც ერთი ელემენტი მასივი, ჩვენ ვიცით, როგორ დასალაგებლად ის. ასე რომ, ხუთ დალაგებულია. ჩვენ უბრალოდ აპირებს განაცხადოს, რომ. ეს არის ერთ ელემენტს მასივი. 

ასე რომ, ჩვენ ახლა დახარისხებული მარცხენა ნახევარში მარცხენა half-- უფრო სწორად, ჩვენ დახარისხებული მარცხენა ნახევარში ფორთოხალი. ასე რომ, ახლა, იმისათვის, რომ ჯერ კიდევ სრული საერთო მასივი მარცხენა ნახევარში, ჩვენ უნდა დასალაგებლად მარჯვენა ნახევარში ფორთოხალი, ან ამ პერსონალი. როგორ უნდა გავაკეთოთ, რომ? ისე, ჩვენ გვაქვს ორი ელემენტს მასივი. ასე რომ, ჩვენ შეგვიძლია დასალაგებლად მარცხენა ნახევარში მასივი, რომელიც ორი. ორი არის ერთ ელემენტს. ასე რომ, ეს გადანაწილებული იყოს. ამის შემდეგ ჩვენ შეგვიძლია დასალაგებლად მარჯვენა ნახევარში რომ ნაწილი მასივი, ერთი. სწორედ ერთგვარი იყოს. 

ეს არის პირველი შემთხვევა, ჩვენ მიაღწია შერწყმა ნაბიჯი. ჩვენ დავასრულეთ, თუმცა ჩვენ ახლა სახის წყობილი დანგრევა და რომ ერთგვარი სახიფათო რამ უკან არის, თქვენ უნდა შეინახოთ თქვენი უხელმძღვანელებს სადაც ჩვენ ვართ. ასე რომ, ჩვენ გვაქვს ერთგვარი მარცხენა ნახევარი ფორთოხალი ნაწილი. 

და ახლა, ჩვენ შუა დახარისხება მარჯვენა ნახევარში ფორთოხალი ნაწილი. და ამ პროცესში, ჩვენ ვართ ახლა უნდა იყოს ნაბიჯი, შერწყმა ორი halves ერთად. როდესაც ჩვენ შევხედოთ ორი halves მასივი, ჩვენ ვხედავთ, ორი და ერთი. რომელი ელემენტი პატარა? ერთ-ერთი. 

მაშინ რომელიც ელემენტს არის პატარა? ისე, ეს ორი ან არაფერი. ასე რომ, ეს ორი. ასე რომ, ახლა, უბრალოდ ერთხელ ვიზრუნოთ სადაც ჩვენ ვართ კონტექსტში, ჩვენ დახარისხებული მარცხენა ნახევარში ფორთოხალი და მარჯვენა ნახევარში წარმოშობის. მე ვიცი, მე შეცვალა ფერები კიდევ ერთხელ, მაგრამ ეს არის ის, სადაც ჩვენ ვიყავით. და მიზეზი მე ეს იმიტომ, რომ ეს პროცესი შენარჩუნება აპირებს, iterating ქვემოთ. ჩვენ დახარისხებული მარცხენა ნახევარი ყოფილი ფორთოხალი და მარჯვენა ნახევარში ყოფილი ფორთოხალი. 

ახლა, ჩვენ უნდა შერწყმა იმ ორი halves ერთად ძალიან. ეს არის ნაბიჯი ჩვენ შესახებ. ასე რომ, ჩვენ მიგვაჩნია, რომ ყველა ელემენტები, რომლებიც ახლა მწვანე, მარცხენა ნახევარში ორიგინალური მასივი. და ჩვენ შერწყმა იმ გამოყენებით იგივე პროცესი ჩვენ გავაკეთეთ შერწყმის ორი და ერთი მხოლოდ ერთი წუთით წინ. 

მარცხენა ნახევარში, პატარა ელემენტს მარცხენა ნახევარი ხუთ. პატარა ელემენტს მარჯვენა ნახევარში ერთ-ერთი. რომელიც იმ არის პატარა? ერთ-ერთი. 

პატარა ელემენტს მარცხენა ნახევარში არის ხუთ. პატარა ელემენტს მარჯვენა ნახევარში ორი. რა არის ყველაზე პატარა? ორი. და მერე ბოლოს და ხუთ არაფერი, ჩვენ შეგვიძლია ვთქვათ, ხუთი. 

OK, ასე რომ დიდი სურათი, მოდით მიიღოს შესვენების მეორე და გაერკვნენ, სადაც ჩვენ ვართ. თუ ჩვენ დავიწყეთ თავიდანვე, ჩვენ ახლა დასრულდა საერთო მასივი მხოლოდ ერთი ნაბიჯი pseudocode კოდი აქ. ჩვენ დახარისხებული მარცხენა ნახევარში მასივი. 

შეგახსენებთ, რომ ორიგინალური იმისათვის, ხუთ, ორი, ერთი. გადის ეს პროცესი და მობუდარი ქვემოთ და იმეორებს, გრძელდება შესვენება პრობლემა ქვემოთ პატარა და მცირე ნაწილები, ჩვენ დავასრულეთ ნაბიჯი ერთი pseudocode მთელი ამოსავალი მასივი. მოვაგვარეთ მისი მარცხენა ნახევარში. 

ახლა მოდით გაყინვას არსებობს. და ახლა მოდით დასალაგებლად მარჯვენა ნახევარი ორიგინალური მასივი. ჩვენ ვაპირებთ, რომ გავაკეთოთ, რომ გადის იგივე განმეორებითი პროცესის დარღვევის რამ down და შემდეგ შერწყმის მათ ერთად. 

ასე რომ მარცხენა ნახევარში წითელი, ან მარცხენა ნახევარში მარჯვენა ნახევარში ორიგინალური მასივი, მე ვაპირებ ვთქვა სამი. ისევ და ისევ, მე, როგორც თანმიმდევრული აქ. თუ თქვენ გაქვთ უცნაური რიგი ელემენტები, ის ნამდვილად არ აქვს მნიშვნელობა თუ არა თქვენ მიიღოს დარჩა ერთი პატარა ან უფლება ერთი პატარა. 

ის არის, რომ, როცა ექმნებათ ამ პრობლემის ჩატარების შერწყმა, თქვენ უნდა იყოს თანმიმდევრული. თქვენ ან ყოველთვის უნდა მიიღოს მარცხენა მხარეს პატარა და ყოველთვის უნდა მიიღოს მარჯვენა მხარეს პატარა. აქ, მე აირჩია, რომ ყოველთვის რათა მარცხენა მხარეს პატარა როდესაც ჩემი მასივი, ან ჩემი ქვე-მასივი, უცნაური ზომა. 

სამი არის ერთ ელემენტს, და ასე რომ დალაგებულია. ჩვენ ჩავატარეთ, რომ ვარაუდი მთელი ჩვენი მთელი პროცესი ჯერჯერობით. ახლა მოდით დასალაგებლად მარჯვენა ნახევარი მარჯვენა ნახევარში, ან მარჯვენა ნახევარში წითელი. 

კიდევ ერთხელ, ჩვენ უნდა გაყოფილი ქვემოთ. ეს არ არის ერთ ელემენტს მასივი. ჩვენ ვერ გამოაცხადოს ის გადანაწილებული. ასე რომ, პირველი, ჩვენ ვაპირებთ დასალაგებლად მარცხენა ნახევარში. 

მარცხენა ნახევარში არის ერთ ელემენტს, ასე რომ, ეს არის ერთგვარი იყოს. მაშინ ჩვენ ვაპირებთ დასალაგებლად მარჯვენა ნახევარი, რომელიც არის ერთ ელემენტს. ეს დალაგებულია იყოს. და ახლა, ჩვენ შეგვიძლია შერწყმა ამ ორი ერთად. ოთხი არის პატარა და მაშინ ექვსი პატარაა. 

ისევ და ისევ, რა გავაკეთეთ ამ ეტაპზე? ჩვენ დახარისხებული მარცხენა ნახევარი მარჯვენა ნახევარში. ან ბრუნდება ორიგინალური ფერები, რომ იქ, ჩვენ დახარისხებული მარცხენა ნახევარი რბილი წითელი. თავდაპირველად ეს იყო მუქი აგურის წითელი და ახლა ეს რბილი წითელი, თუ ეს იყო რბილი წითელი. 

და მაშინ ჩვენ დახარისხებული მარჯვენა ნახევარში რბილი წითელი. ახლა, კარგად, ისინი მწვანე ერთხელ, მხოლოდ იმიტომ, რომ ჩვენ ვაპირებთ მეშვეობით პროცესში. და ჩვენ უნდა გავიმეოროთ მეტი და მეტი. 

ასე რომ, ახლა ჩვენ შეგვიძლია შერწყმა ამ ორი halves ერთად. და რომ ის, რასაც ჩვენ ვაკეთებთ აქ. ასე რომ, შავი ხაზი მხოლოდ იყოფა მარცხენა ნახევარში და მარჯვენა ნახევარში ამ სახის ნაწილი. 

შევადარებთ პატარა ღირებულება მარცხენა მხარეს მასივი ან მაპატიეთ, პატარა მნიშვნელობა მარცხენა ნახევარში რომ მცირე ღირებულების მარჯვენა ნახევარი და ნახავთ, რომ სამი პატარა. ახლა ცოტა ოპტიმიზაცია, არა? არსებობს რეალურად არაფერი მარცხენა მარცხენა მხარეს. 

არაფერია დარჩენილი მარცხენა მხარეს, ასე რომ ჩვენ შეგვიძლია ეფექტურად უბრალოდ move-- ჩვენ შეგვიძლია განვაცხადოთ, დანარჩენი ეს არის რეალურად დახარისხებული და მხოლოდ Tack ეს , იმიტომ, რომ იქ არაფერი სხვა შედარების წინააღმდეგ. ჩვენ ვიცით, რომ მარჯვენა მხარეს მარჯვენა მხარეს არის გადანაწილებული. 

OK, ასე რომ, ახლა მოდით გაყინვას ერთხელ და გაერკვნენ, სადაც ჩვენ ვართ ამბავი. საერთო მასივი, რა ჩვენ დასრულებულა? ჩვენ რეალურად განახორციელოს ახლა ნაბიჯები ერთი და ნაბიჯი ორი. ჩვენ დახარისხებული მარცხენა ნახევარში, და ჩვენ დახარისხებული მარჯვენა ნახევარში. 

ახლა, ყველა რომ რჩება ჩვენთვის შერწყმა ამ ორი halves ერთად. ასე რომ, ჩვენ შევადარებთ ყველაზე დაბალი ღირებულება ელემენტის თითოეულ ნახევარში მასივი თავის მხრივ, და გაგრძელება. ერთი ნაკლებია, ვიდრე სამი, ასე რომ ერთი მიდის. 

ორი ნაკლებია, ვიდრე სამი, ასე ორი მიდის. სამი ნაკლებია, ვიდრე 5, ამიტომ სამი მიდის. ოთხი ნაკლებია, ვიდრე 5, ამიტომ ოთხი მიდის. ხუთ ნაკლებია, ვიდრე ექვსი, და ექვსი არის ყველა, რომ რჩება. 

ახლა, მე ვიცი, რომ იყო ბევრი ნაბიჯები. და ჩვენ დაუტოვებიათ ბევრი მეხსიერების ჩვენს გოლი. და რომ ის, რაც იმ ნაცრისფერი მოედნებზე. და ეს, ალბათ იგრძნო, როგორიცაა, რომ აიღო ბევრი უმეტეს Insertion დალაგების, bubble დალაგების, ან შერჩევა ერთგვარი. 

მაგრამ რეალურად, იმიტომ, რომ ბევრი ამ პროცესებში ხდება ამავე time-- რასაც ჩვენ გამოგიგზავნით, კიდევ ერთხელ, ლაპარაკი, როდესაც ჩვენ ვსაუბრობთ უკან მომავალში ვიდეოში ეს ალგორითმი რეალურად ნათლად არის ფუნდამენტურად განსხვავებული, ვიდრე არაფერი ჩვენ ვნახეთ ადრე მაგრამ ასევე მნიშვნელოვნად უფრო ეფექტური. 

რატომ არის, რომ? ისე, ყველაზე ცუდი შემთხვევაში, ჩვენ გვაქვს გაყოფილი n ელემენტებით და შემდეგ recombine მათ. მაგრამ, როდესაც ჩვენ recombine მათ, თუ რას ვაკეთებთ ძირითადად გაორმაგდა ზომა პატარა მასივები. ჩვენ გვყავს bunch ერთ ელემენტს კოლექტორები რომ ჩვენ ეფექტურად აერთიანებს ორ ელემენტს მასივები. და მაშინ ჩვენ მიიღოს იმ ორი ელემენტი კოლექტორები და აერთიანებს მათ ერთად ოთხი ელემენტი მასივები, და ასე შემდეგ, და ასე შემდეგ, და ასე შემდეგ, სანამ ჩვენ აქვს ერთი n ელემენტს მასივი. 

მაგრამ რამდენი გამეორებებები სჭირდება მისაღებად N? გაიხსენეთ სატელეფონო წიგნი მაგალითად. რამდენჯერ ჩვენ უნდა გაანადგურეს სატელეფონო წიგნი ნახევარი, კიდევ რამდენი ჯერ ჩვენ უნდა გაანადგურეს სატელეფონო წიგნი ნახევარი, თუ ზომის სატელეფონო წიგნი გაორმაგდა? არსებობს მხოლოდ ერთი, არა? 

ასე რომ, არსებობს გარკვეული ლოგარითმული ელემენტი აქ. მაგრამ ჩვენ ასევე ჯერ კიდევ აქვს მინიმუმ შევხედოთ ყველა n ელემენტებს. ასე რომ, უარეს შემთხვევაში, შერწყმა დალაგების ეშვება ო ჟურნალი ო. ჩვენ უნდა შევხედოთ ყველა ო ელემენტები, და ჩვენ უნდა დააკავშიროთ მათ ერთად log n კომპლექტი ნაბიჯები. საუკეთესო შემთხვევაში, მასივი კარგად გადანაწილებული. სწორედ დიდი. მაგრამ საფუძველზე ალგორითმი გვაქვს აქ, ჩვენ ჯერ კიდევ გვაქვს გაყოფილი და recombine. მიუხედავად იმისა, რომ ამ შემთხვევაში, recombining სახის არაეფექტური. ეს არ არის საჭირო. მაგრამ ჩვენ მაინც გაიაროს მთელი პროცესი მაინც. 

ასე რომ, საუკეთესო შემთხვევაში და უარეს შემთხვევაში, ეს ალგორითმი ეშვება N შესვლა N დრო. შერწყმა დალაგების ნამდვილად ცოტა უფრო რთული ვიდრე სხვა ძირითადი დახარისხება ალგორითმები ჩვენ ვისაუბრეთ CS50, მაგრამ არსებითად უფრო ძლიერი. 

ასე რომ, თუ თქვენ ოდესმე შემთხვევა სჭირდება ან გამოიყენოს იგი დასალაგებლად დიდი მონაცემები კომპლექტი, მიღების თქვენი უფროსი გარშემო იდეა უკან იქნება მართლაც ძლიერი. და ის აპირებს, რომ თქვენი პროგრამები ნამდვილად ბევრად უფრო ეფექტური გამოყენებით შერწყმა დალაგების წინააღმდეგ არაფერი. მე Doug Lloyd. ეს არის CS50.