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

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

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

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

მაშინ ჩვენ ვიმეორებ ეს პროცესი until-- ჩვენ გავიმეორო შემდეგ პროცესი სანამ ყველა ელემენტები დალაგებულია. შეხედეთ შემდეგი არასორტირებული ელემენტს და ჩადეთ იგი დახარისხებული ნაწილი, გადასვლის საჭირო რაოდენობის ელემენტების გარეთ გზა. იმედია ეს ვიზუალიზაცია დაეხმარება ხედავთ ზუსტად რა ხდება Insertion დალაგების. 

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

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

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

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

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

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

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

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

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

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

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

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

იმ შემთხვევაში, თუ მასივი მშვენივრად დალაგებულია, ყველა ჩვენ უნდა გავაკეთოთ არის შევხედოთ თითოეული ელემენტი ერთხელ, და მაშინ ჩვენ გავაკეთეთ. ასე რომ, საუკეთესო შემთხვევაში, ეს omega of ო. 

მე Doug Lloyd. ეს არის CS50.