[Powered by Google Translate] [შერწყმა დალაგების] [Rob Bowden - ჰარვარდის უნივერსიტეტი] [ეს არის CS50. - CS50.TV] ვისაუბროთ იმაზე შერწყმა ჯიშია. ჯერჯერობით თქვენ ვხედავთ bubble sort, Insertion დალაგების, და შერჩევის ჯიშია. მიუხედავად იმისა, რომ მე სახის ტალღა ჩემი ხელი რას ვგულისხმობ მიერ უკეთესი, შერწყმა დალაგების ზოგადად ასრულებს უკეთესი, ვიდრე ნებისმიერი ამ 3 სახეობის. 

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

თუმცა ეს სამუშაოები, ეს ბევრი ზედმეტი მუშაობა. ჩვენ შეგვიძლია ამის გაკეთება სწრაფად, ვიდრე უბრალოდ დახარისხება. გაითვალისწინეთ, რომ ერთი არასწორი იდეა, რომ მხოლოდ მიიღოს ალტერნატიული თასები თითოეული სიაში. მიუხედავად იმისა, რომ ჩანდეს, როგორიცაა, რომ სამუშაოების პირველი, აკეთებს, რომ ჩვენ დასრულდება მდე მქონე 4, 8, 15, 23, 16 - ცნობა 16 და 23 გამოსულია ადგილი. ეს იმიტომ რომ 2 ელემენტს, რომლებიც უნდა გამოჩნდეს თანმიმდევრული შერწყმული სია რომლებიც არიან იგივე საწყის სიაში. ორივე 15 და 16 არიან სიაში მარცხენა. ხრიკი არის ისარგებლოს იმ ფაქტს, რომ ორივე სიები უკვე დახარისხებული. ეს ნიშნავს, რომ თუ ჩვენ შევჩერდეთ პირველი ელემენტები ორივე სიები - აქ, 4 და 8 - ერთი მათგანი უნდა იყოს პირველ ელემენტს შერწყმული სიაში. ისე, რატომ არის, რომ? ორივე ეს სიები უკვე დახარისხებული, და ა.შ. ან 4 ან 8 უნდა იყოს პატარა ელემენტს, როდესაც ჩვენ დააკავშიროთ 2 სიები. ამ შემთხვევაში, ყველაზე პატარა არის 4, ამიტომ ჩვენ შეგვიძლია აიღოს 4 და გახდეს პირველი ელემენტს ჩვენი შერწყმული სიაში. ახლა ჩვენ გავაგრძელებთ შერწყმის დარჩენილი 3 ელემენტები პირველი სიაში და 4 ელემენტები მეორე სიაში. 

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

გაითვალისწინეთ, რომ 2 ელემენტები მოვიდა იმავე სიაში in a row. ამიტომ გაერთიანებული სიაში არ შეუძლიათ უბრალოდ ალტერნატიული ელემენტების 2 სიები. შედარება 50 და 23, 23 პატარაა, ამიტომ ვირჩევთ რომ. შორის 50 და 42, 42 პატარაა. შორის 50 და 108, 50 პატარაა. და ბოლოს, ჩვენ უბრალოდ უნდა 108, ასე რომ უნდა წავიდეს წლის ბოლომდე ჩვენს სიაში. გაითვალისწინეთ, რომ ჩვენ გვაქვს ლამაზი, დახარისხებული სია. ყოველ ჯერზე ჩვენ შედარებით პირველი 2 ელემენტები 2 სიები ჩვენ შევძელით, რათა დადგინდეს შემდეგი ელემენტს შერწყმული სიაში. ეს ნიშნავს, რომ თუ საბოლოო სია შეიცავს N ნომრები, სადაც n აქ არის 8, მაშინ ჩვენ გვჭირდება საუკეთესო N შედარებები მისაღებად ყველა იმ ნომრები სწორი ადგილი. ასეთი ალგორითმი განაცხადა გასაშვებად წელს ხაზოვანი დროს, მაგრამ არ ინერვიულოთ შესახებ, რომ აქ. 

ჩვენი ალგორითმი შერწყმის, შეიძლება გავაკეთოთ სწრაფი შერწყმა დახარისხების ალგორითმი. ასე რომ, მოდით აღადგინოთ ჩვენი სიები. არის 2 დიდი ნაბიჯები პროცესში შერწყმა ჯიშია. პირველი, განუწყვეტლივ გაყოფილი სიაში შევიდა თასები halves სანამ ჩვენ გვაქვს bunch of სიები მხოლოდ 1 ჭიქა მათში. არ ინერვიულოთ, თუ სია შეიცავს კენტი ნომერი და ვერ მიიღოს შესანიშნავად სუფთა cut მათ შორის. უბრალოდ თვითნებურად აირჩიოთ რომელიც სიაში შედის ზედმეტი თასი სისტემაში ასე რომ, მოდით, გაყოფილი ამ სიებში. ახლა ჩვენ გვაქვს 2 სიები. ახლა ჩვენ გვაქვს 4 სიები. 

და ახლა ჩვენ გვაქვს 8 სიები ერთი ჭიქა ყოველ სიაში. ასე რომ ეს ნაბიჯი 1. ამისთვის ნაბიჯი 2, ჩვენ არაერთხელ შერწყმა წყვილი სიები გამოყენებით შერწყმა ალგორითმი გავიგეთ ადრე. შერწყმა 108 და 15, ჩვენ დასრულდება up ერთად სიაში 15, 108. შერწყმა და 50 4, ჩვენ დასრულდება up ერთად 4, 50. შერწყმა 8 და 42 ჩვენ დასრულდება მდე, 8, 42. და შერწყმის 23 და 16, ჩვენ დასრულდება მდე, 16, 23. ახლა ყველა ჩვენი სიები არის ზომა 2. გაითვალისწინეთ, რომ ყოველი 4 სიები დალაგებულია. 

ასე რომ ჩვენ შეგვიძლია დავიწყოთ შერწყმის წყვილი სიები კიდევ ერთხელ. შერწყმა 15 და 108 და 4 და 50 - პირველი მიიღოს 4, შემდეგ 15, მაშინ 50, მაშინ 108. შერწყმა 8, 42 და 16, 23, ჩვენ პირველი მიიღოს 8, შემდეგ 16, მაშინ 23, მაშინ 42. ახლა ჩვენ გვაქვს მხოლოდ 2 სიები ზომა 4, რომელთაგან თითოეული დალაგებულია. ახლა ჩვენ შევაერთებთ ამ 2 სიები. პირველი ჩვენ ვიღებთ 4. მაშინ ჩვენ ვიღებთ 8. მაშინ ჩვენ ვიღებთ 15 და 16, მერე 23, მერე 42, მერე 50, მერე 108. და ჩვენ გავაკეთეთ. ჩვენ ახლა აქვს დახარისხებული სია. ასე რომ რამდენად სწრაფად იყო ეს ზუსტად? ტექნიკური თვალსაზრისით, შერწყმა დალაგების არის O (N შესვლა N), ხოლო ყველა bubble sort, Insertion დალაგების, და შერჩევის დალაგების are O (N ²). სინამდვილეში, როგორც თქვენ შეიტყობს, თქვენ ვერ შეძლებთ ამუშავება დალაგება რომელიც ახორციელებს უკეთესად O (N შესვლა N) ზოგად შემთხვევაში. ერთხელ, არ ინერვიულოთ შესახებ დიდი O ნოტაცია თუ არ მინახავს ეს არავის გაუკეთებია. 

უბრალოდ ვიცი, რომ ეს იმას ნიშნავს, თუ გვინდოდა დასალაგებლად მართლაც დიდი სია bubble sort, Insertion დალაგების, და შერჩევის დალაგების შესაძლოა მიიღოს მნიშვნელოვნად აღემატება შერწყმა ჯიშია. ეს არ ნიშნავს, რომ შერწყმა დალაგების იქნება უფრო სწრაფად ყველა სიები ან თუნდაც ნებისმიერი ერთიანი სია ქვეშ გარკვეული ზომით. მაგალითად, Insertion დალაგება შეიძლება იყოს უსწრაფესი დალაგების ყველა სიები ნაკლებია 5 ელემენტებს. პრაქტიკაში, შერწყმა დალაგების ჩვეულებრივ სწრაფად ამისთვის სიები როგორც პატარა, როგორც 50 ელემენტებს. 

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

ჩემი სახელი არის რობ Bowden, და ეს არის CS50. [CS50.TV] - და შერჩევის ჯიშია. [იცინის] ოჰ, მივიღე მიიღოს, რომ რადგან მე გადაირთვება როგორ ვიყავი წარდგენა. სია მარცხენა. ეს იყო typo. [Misspoke] მე ბრალია - [იცინის] მე არ ვიცი, რა -