[Powered by Google Translate] [Insertion დალაგების]
[Tommy MacWilliam] [ჰარვარდის უნივერსიტეტის]
[ეს არის CS50.TV]
მოდით შევხედოთ Insertion დახარისხების, ალგორითმი აღების სიაში ნომრები და დახარისხება მათ.
ალგორითმი, გახსოვდეთ, უბრალოდ ნაბიჯ ნაბიჯ პროცედურა განხორციელების ამოცანა.
ძირითადი იდეა უკან Insertion დახარისხების, არის გაყავით ჩვენს სიაში შევიდა ორი ნაწილი, რომლებიც
დახარისხებული ნაწილი და არასორტირებული ნაწილი.
>> ყოველ ნაბიჯი ალგორითმი, ნომერი გადავიდა
საწყისი არასორტირებული ნაწილი უნდა დალაგებულია ნაწილი
სანამ საბოლოოდ მთელი სია დალაგებულია.
აქ არის ჩამონათვალი ექვსი არასორტირებული ნომრები - 23, 42, 4, 16, 8 და 15.
რადგან ეს ციფრები არ არის ყველა აღმავალი შეკვეთა, ისინი არასორტირებული.
ვინაიდან ჩვენ არ დაწყებულა დახარისხება ჯერჯერობით, ჩვენ განიხილავს ექვსივე ელემენტები ჩვენი არასორტირებული ნაწილი.
>> ერთხელ ჩვენ ვიწყებთ დახარისხება, ჩვენ დააყენა ამ დახარისხებული ნომრის მარცხენა ამათგანი.
ასე რომ, დავიწყოთ 23, პირველი ელემენტია ჩვენს სიაში.
ჩვენ არ გვაქვს რაიმე ელემენტების ჩვენი დახარისხებული ნაწილი მაინც,
მოდით უბრალოდ განიხილოს 23 იქნება დაწყების და დასრულების ჩვენი დახარისხებული ნაწილი.
ახლა ჩვენს დახარისხებული ნაწილი აქვს ერთი ნომერი, 23,
და ჩვენი არასორტირებული ნაწილი აქვს ამ ხუთი ნომრები.
მოდით ახლა ჩადეთ შემდეგი რაოდენობის ჩვენს არასორტირებული ნაწილი, 42, შევიდა დახარისხებული ნაწილი.
>> ამისათვის ჩვენ უნდა შეადაროთ 42 დან 23 - მხოლოდ ელემენტს ჩვენს დახარისხებული ნაწილი ჯერჯერობით.
ორმოცდაორ აღემატება 23, ასე რომ ჩვენ შეგვიძლია უბრალოდ დამატება 42 ბოლომდე
საქართველოს დახარისხებული ნაწილი სიაში. მშვენიერია
ახლა ჩვენი დახარისხებული ნაწილი აქვს ორი ელემენტები და ჩვენი არასორტირებული ნაწილი ოთხი ელემენტები.
ასე რომ, მოდით, ახლა გადავა 4, შემდეგი ელემენტია არასორტირებული ნაწილი.
ასე რომ, სადაც უნდა ამ განთავსდება დახარისხებული ნაწილი?
>> გახსოვდეთ, ჩვენ გვინდა განათავსებს ამ რაოდენობის დახარისხებული მიზნით
ამიტომ ჩვენი დახარისხებული ნაწილი რჩება სწორად დალაგებულია ნებისმიერ დროს.
თუ ჩვენ განათავსებს 4 მარჯვნივ 42, მაშინ ჩვენი სიიდან იქნება მწყობრიდან.
ასე რომ, მოდით, გავაგრძელოთ მოძრავი უფლება-ის მარცხენა ჩვენს დალაგების ნაწილი.
როგორც ჩვენ გადავა, მოდით გადაეტანა თითოეული ნომრის ქვემოთ ადგილი, რათა ოთახის ახალი ნომერი.
Okay, 4 ასევე ნაკლები 23, ამიტომ ჩვენ ვერ შეძლებს აქ არც.
მოდით გადაადგილება 23 უფლება ერთ ადგილას.
>> ეს იმას ნიშნავს, ჩვენ გვინდა განვათავსოთ 4 შევიდა პირველი სლოტი წელს დახარისხებული ნაწილი.
შეამჩნევთ, თუ როგორ ამ სივრცეში სიაში იყო უკვე დაცარიელდა,
იმიტომ, რომ ჩვენ უკვე მოძრავი დახარისხებული ელემენტების ქვემოთ როგორც ჩვენ შეექმნა მათ.
ყველა უფლება. ასე რომ, ჩვენ შუა ნაწილამდე იყვნენ იქ.
მოდით გავაგრძელოთ ალგორითმი მიერ ჩასმა 16 შევიდა დახარისხებული ნაწილი.
თექვსმეტი ნაკლებია, ვიდრე 42, მოდით გადაეტანა 42 მარჯვნივ.
თექვსმეტი ასევე ნაკლები 23, მოდით ასევე გადაეტანა, რომ ელემენტს.
>> ახლა, 16 მეტია 4. ასე რომ, როგორც ჩანს მინდა ჩადეთ 16 შორის 4 და 23.
მიუხედავად იმისა, მოძრავი მეშვეობით დახარისხებული ნაწილი სიაში მარჯვნიდან მარცხნივ,
4 არის პირველი ნომერი ჩვენ ვნახეთ, რომ მცირეა ნომერი
ჩვენ ვცდილობთ ჩასასმელად.
ასე რომ, ახლა ჩვენ ჩადეთ 16 ამ ცარიელ ჭრილში,
რომელიც, გახსოვდეთ, ჩვენ მიერ შექმნილი მოძრავი ელემენტების დალაგების ნაწილი დასრულდა
როგორც ჩვენ შეექმნა მათ.
>> ყველა უფლება. ახლა ჩვენ გვყავს ოთხი დახარისხებული ელემენტები და ორი არასორტირებული ელემენტებს.
ასე რომ, მოდით, გადაადგილება 8 შევიდა დახარისხებული ნაწილი.
რვა ნაკლებია, ვიდრე 42.
რვა ნაკლებია, ვიდრე 23.
და 8 ნაკლებია, ვიდრე 16.
მაგრამ 8 მეტია 4.
ასე რომ, მინდა ჩადეთ 8 შორის 4 და 16.
და ახლა ჩვენ უბრალოდ კიდევ ერთი ელემენტს დაუტოვებიათ დასალაგებლად - 15.
თხუთმეტი ნაკლებია, ვიდრე 42,
თხუთმეტი ნაკლებია, ვიდრე 23.
და 15 ზე ნაკლებია 16.
მაგრამ 15 მეტია 8.
>> ასე რომ, აქ არის, სადაც ჩვენ გვინდა, რომ ჩვენი საბოლოო Insertion.
და ჩვენ გავაკეთეთ.
ჩვენ არ გვაქვს მეტი ელემენტების არასორტირებული ნაწილი,
და ჩვენი დახარისხებული ნაწილი არის სწორი მიზნით.
ციფრები დავალება ყველაზე პატარა რომ უდიდესი.
ასე რომ, მოდით შევხედოთ ზოგიერთი pseudocode რომელიც ასახავს ნაბიჯებით ჩვენ მხოლოდ შესრულებული.
>> On line 1, ვხედავთ, რომ ჩვენ გვჭირდება iterate მეტი თითოეული ელემენტის სიაში
გარდა პირველი, რადგან პირველი ელემენტია არასორტირებული ნაწილი უბრალოდ გახდეს
პირველი ელემენტია დახარისხებული ნაწილი.
On ხაზები 2 და 3, ჩვენ შენახვა ტრეკზე ჩვენი დღევანდელი ადგილი არასორტირებული ნაწილი.
Element წარმოადგენს პუნქტების ჩვენ გაკეთებული მოძრავი შევიდა დახარისხებული ნაწილი,
და კ წარმოადგენს ჩვენი ინდექსი შევიდა არასორტირებული ნაწილი.
>> On line 4, ჩვენ iterating მეშვეობით დახარისხებული ნაწილი მარჯვნიდან მარცხნივ.
ჩვენ გვინდა, რომ შეწყვიტოს iterating ერთხელ ელემენტს მარცხნივ ჩვენი მიმდინარე თანამდებობა
ნაკლებია, ვიდრე ელემენტს ვცდილობთ ჩადეთ.
On line 5, ჩვენ გადავიდა ყოველ ელემენტს ვხვდებით ერთ სივრცეში უფლება.
ამ გზით, ჩვენ გვექნება ნათელი სივრცე INSERT INTO როდესაც ჩვენ პირველად ელემენტს
ნაკლებია, ვიდრე ელემენტს ჩვენ მოძრავი.
On line 6, ჩვენ განახლებაზე ჩვენი Counter გააგრძელოს გადაადგილება დაუტოვებიათ მეშვეობით დახარისხებული ნაწილი.
საბოლოოდ, on line 7, ჩვენ ჩასმა ელემენტს შევიდა დახარისხებული ნაწილი სიაში.
>> ჩვენ ვიცით, რომ ეს okay ჩასასმელად შევიდა პოზიცია j,
იმიტომ, რომ ჩვენ უკვე გადავიდა ელემენტს, რომლებიც იქ ერთ სივრცეში უფლება.
გახსოვდეთ, ჩვენ მოძრავი მეშვეობით დახარისხებული ნაწილი მარჯვნიდან მარცხნივ,
მაგრამ ჩვენ მოძრავი მეშვეობით არასორტირებული ნაწილი მარცხნიდან მარჯვნივ.
ყველა უფლება. მოდით ახლა შეხედეთ, რამდენი ხანი გაშვებული რომ ალგორითმი აიღო.
ჩვენ ვთხოვთ პირველი კითხვა, რამდენი ხანი სჭირდება ამ ალგორითმის გასაშვებად ყველაზე ცუდ შემთხვევაში.
შეგახსენებთ, რომ წარმოვადგენთ ამ გაშვებული დროის დიდი O ნოტაცია.
იმისათვის, რომ დასალაგებლად ჩვენს სიაში, მოგვიწია iterate მეტი ელემენტების არასორტირებული ნაწილი,
და თითოეული იმ ელემენტებს, პოტენციურად ყველა ელემენტების დახარისხებული ნაწილი.
ინტუიციურად, ამ ჟღერს O (N ^ 2) ოპერაცია.
>> ეძებს ჩვენს pseudocode, ჩვენ გვაქვს loop წყობილი შიგნით კიდევ ერთი მარყუჟი,
რაც, რა თქმა უნდა, ჟღერს O (N ^ 2) ოპერაცია.
თუმცა, დახარისხებული ნაწილი სიაში არ შეიცავს მთელ სიაში, სანამ ბოლომდე.
მიუხედავად ამისა, ჩვენ შესაძლოა ჩადეთ ახალ ელემენტს დროს ძალიან დასაწყისში დახარისხებული ნაწილი
ყოველ iteration of ალგორითმი,
რაც იმას ნიშნავს, რომ ჩვენ გვინდა უნდა შევხედოთ თითოეული ელემენტის ამჟამად დახარისხებული ნაწილი.
ასე რომ, ეს ნიშნავს, რომ ჩვენ შესაძლოა ერთი შედარებით მეორე ელემენტს,
ორი შედარებები მესამე ელემენტს, და ასე შემდეგ.
ასე რომ, სულ რამდენიმე ისეთი ნაბიჯი არის თანხა რიცხვებით 1 დან სიგრძე სიის მინუს 1.
ჩვენ შეგვიძლია წარმოადგენენ ამ summation.
>> ჩვენ არ წასვლას summations აქ, მაგრამ აღმოჩნდება, რომ ამ summation უდრის
n (n - 1) მეტი 2, რომელიც უდრის N ^ 2/2 - N / 2.
როდესაც ვსაუბრობთ asymptotic Runtime,
ამ N ^ 2 ვადით აპირებს დომინირება ამ N ვადით.
ასე რომ, Insertion დალაგების არის დიდი O (N ^ 2).
რა მოხდება, თუ ჩვენ გაიქცა Insertion დალაგების შესახებ უკვე დახარისხებული სია.
ამ შემთხვევაში, ჩვენ გვინდა უბრალოდ დაამყარონ დახარისხებული ნაწილი მარცხნიდან მარჯვნივ.
ასე რომ, ჩვენ მხოლოდ უნდა ბრძანებით N ნაბიჯები.
>> ეს იმას ნიშნავს, რომ Insertion დალაგების აქვს საუკეთესო შემთხვევაში შესრულება N,
რომელსაც ჩვენ წარმოვადგენთ ერთად Ω (N).
სწორედ ეს Insertion დახარისხების,
მხოლოდ ერთი ბევრი ალგორითმები ჩვენ შეგვიძლია გამოვიყენოთ დასალაგებლად სიაში.
ჩემი სახელი არის ტომი, და ეს არის CS50.
[CS50.TV]
ოჰ, თქვენ უბრალოდ ვერ შეაჩერებს, რომ ერთხელ იწყება.
ოჰ, ჩვენ რომ - >> BooM!