[Powered by Google Translate] ტომი: მოდით შევხედოთ შერჩევის დახარისხების, ალგორითმი
აღების სიაში ნომრები და დახარისხება მათ.
ალგორითმი, გახსოვდეთ, უბრალოდ ნაბიჯ ნაბიჯ
პროცედურა განხორციელების ამოცანა.
ძირითადი იდეა უკან შერჩევის დალაგების არის გაყავით
ჩვენს სიაში შევიდა ორი ნაწილი -
დახარისხებული ნაწილი და არასორტირებული ნაწილი.
ყოველ ნაბიჯი ალგორითმი, ნომერი გადაინაცვლა
არასორტირებული ნაწილი უნდა დალაგებულია ნაწილი სანამ საბოლოოდ
მთელი სია დალაგებულია.
ასე რომ აქ სიაში ექვსი ნომერი -
23, 42, 4, 16, 8 და 15.
ახლავე სრული სია ითვლება არასორტირებული.
მიუხედავად იმისა, რომ ხმების მოსწონს 16 შესაძლოა უკვე მისი სწორი
საიდან, ჩვენი ალგორითმი აქვს არანაირად არ იცის, რომ სანამ
მთელი სია დალაგებულია.
ამიტომ ჩვენ განიხილოს ყველა ნომერი უნდა არასორტირებული სანამ ჩვენ დასალაგებლად
იგი საკუთარ თავს.
ჩვენ ვიცით, რომ ჩვენ გვინდა სია უნდა იყოს აღმავალი შეკვეთა.
ასე რომ ჩვენ გვინდა, რომ დაამყარონ დახარისხებული ნაწილი ჩვენს სიაში
მარცხნიდან მარჯვნივ, პატარა, რათა უმსხვილესი.
ამისათვის, ჩვენ გვჭირდება, მინიმუმ არასორტირებული ელემენტს
და განათავსოთ დასასრულს დახარისხებული ნაწილი.
მას შემდეგ, რაც ამ სიაში არ არის დახარისხებული, ერთადერთი გზა ამის გაკეთება არის
შეხედეთ თითოეულ ელემენტს არასორტირებული ნაწილი, დამახსოვრების
რომელიც ელემენტს არის ყველაზე დაბალი და შედარებით
ყოველ ელემენტს რომ.
ასე რომ ჩვენ პირველი შევხედოთ 23.
ეს არის პირველი ელემენტს ჩვენ ვნახეთ, ასე რომ ჩვენ გვახსოვს
მას როგორც მინიმუმ.
შემდეგი ჩვენ შევხედოთ 42.
42 აღემატება 23, ასე 23 ჯერ კიდევ მინიმუმ.
შემდეგი არის 4 ნაკლებია 23, ამიტომ ჩვენ გვახსოვს 4
როგორც ახალი მინიმალური.
შემდეგი არის 16 რომელიც აღემატება 4, ასე 4
ჯერ კიდევ მინიმუმ.
8 აღემატება 4 და 15 აღემატება 4, ისე 4 უნდა იყოს
ყველაზე პატარა არასორტირებული ელემენტს.
ასე რომ მიუხედავად იმისა, რომ როგორც ადამიანები შეგვიძლია დაუყოვნებლივ ვხედავთ, რომ 4 არის
მინიმალური ელემენტის, ჩვენი ალგორითმი სჭირდება შევხედოთ
ყველა არასორტირებული ელემენტს შემდეგაც კი, ჩვენ ნაპოვნია 4 -
მინიმალური ელემენტს.
ახლა რომ ჩვენ ი მინიმალური ელემენტს, 4, ჩვენ გვინდა
მისი გადატანა შევიდა დახარისხებული ნაწილი სიაში.
რადგან ეს არის პირველი ნაბიჯი, ეს იმას ნიშნავს, რომ ჩვენ გვინდა დააყენა 4 საათზე
დასაწყისში სიაში.
ახლავე 23 არის დასაწყისში სიაში, ასე
მოდით სვოპ 4 და 23.
ახლა ჩვენს სიაში ასე გამოიყურება.
ჩვენ ვიცით, რომ 4 უნდა იყოს საბოლოო საიდან, რადგან ეს
ორივე პატარა ელემენტს და ელემენტს დასაწყისში
სიის.
ასე რომ, ეს იმას ნიშნავს, რომ ჩვენ არ გვჭირდება ოდესმე მისი გადატანა კიდევ ერთხელ.
მოდით ვიმეორებ, რომ ეს პროცესი დაამატოთ კიდევ ერთი ელემენტი
დახარისხებული ნაწილი სიაში.
ჩვენ ვიცით, რომ ჩვენ არ უნდა შევხედოთ 4, იმიტომ რომ
უკვე დახარისხებული.
ასე რომ ჩვენ შეგვიძლია იწყება 42, რომელიც ჩვენ გვახსოვს, როგორც
მინიმალური ელემენტს.
ასე რომ შემდეგი ჩვენ შევხედოთ 23 ნაკლებია 42, ამიტომ ჩვენ
გვახსოვდეს 23 არის ახალი მინიმალური.
შემდეგი ჩვენ ვხედავთ 16 ნაკლებია 23, ისე
16 არის ახალი მინიმალური.
ახლა ჩვენ შევხედოთ 8 ნაკლებია 16, ისე
8 არის ახალი მინიმალური.
და ბოლოს 8 ნაკლებია, ვიდრე 15, ასე რომ, ჩვენ ვიცით, რომ 8 არის მინიმუმი
არასორტირებული ელემენტს.
ასე რომ, რაც იმას ნიშნავს, რომ ჩვენ უნდა დამატება 8 დან დახარისხებული
ნაწილი სიაში.
ახლავე 4 არის მხოლოდ დახარისხებული ელემენტს, ამიტომ ჩვენ გვინდა განათავსებს
8 შემდეგი 4.
მას შემდეგ, რაც 42 არის პირველი ელემენტია არასორტირებული ნაწილი
სია, ჩვენ გვინდა, რომ სვოპ 42 და 8.
ახლა ჩვენს სიაში ასე გამოიყურება.
4 და 8 წარმოადგენენ დახარისხებული ნაწილი სიაში, და
დარჩენილი ციფრები წარმოადგენენ არასორტირებული
ნაწილი სიაში.
მოდით გავაგრძელოთ სხვა iteration.
ჩვენ დავიწყებთ 23 ამ დროს, რადგან ჩვენ არ გვჭირდება შევხედოთ
4 და 8 უქმნით რადგან ისინი
უკვე დახარისხებული.
16 ნაკლებია, ვიდრე 23, ამიტომ ჩვენ გვახსოვს
16 როგორც მინიმუმ ახალი.
16 ნაკლებია, ვიდრე 42, მაგრამ 15 ზე ნაკლებია 16, ისე 15 უნდა იყოს
მინიმალური არასორტირებული ელემენტს.
ახლა ჩვენ გვინდა სვოპ 15 და 23 დან
მოგვცეს ამ სიაში.
დახარისხებული ნაწილი სია შედგება 4, 8 და 15, და
ამ ელემენტების კვლავ არასორტირებული.
მაგრამ ეს ასე მოხდება, რომ შემდეგი არასორტირებული ელემენტს, 16,
უკვე დახარისხებული.
თუმცა, არ არსებობს გზა ჩვენს ალგორითმი, რათა იცოდეს, რომ 16
უკვე მისი სწორი მდებარეობა, ამიტომ ჩვენ კვლავ უნდა
ვიმეორებ ზუსტად იგივე პროცესი.
ასე რომ, ჩვენ ვხედავთ, რომ 16 ნაკლებია, ვიდრე 42 და 16 არის ნაკლები ვიდრე 23, ისე
16 უნდა იყოს მინიმუმ ელემენტს.
შეუძლებელია სვოპ ამ ელემენტს საკუთარ თავთან, რათა
უბრალოდ დატოვეთ ამ ადგილას.
ამიტომ, ჩვენ გვჭირდება კიდევ ერთი უღელტეხილი ჩვენი ალგორითმი.
42 მეტია 23, ისე 23 უნდა იყოს
მინიმალური არასორტირებული ელემენტს.
ერთხელ ჩვენ სვოპ 23 და 42, ჩვენ დასრულდება მდე ჩვენს საბოლოო
დახარისხებული სია -
4, 8, 15, 16, 23, 42.
ჩვენ ვიცით, 42 უნდა იყოს სწორი ადგილი, რადგან ეს
მხოლოდ ელემენტს დაუტოვებიათ, და ეს შერჩევის ჯიშია.
მოდით ახლა formalize ჩვენი ალგორითმი რამდენიმე
pseudocode.
On line ერთი, ჩვენ ვხედავთ, რომ ჩვენ გვჭირდება ინტეგრაცია ზე მეტი
ყოველ ელემენტს სიაში.
გარდა ბოლო ელემენტს, რადგან 1 ელემენტს
სიაში უკვე დახარისხებული.
On line ორი, მიგვაჩნია პირველი ელემენტს არასორტირებული
ნაწილი სიაში უნდა იყოს მინიმალური, როგორც გავაკეთეთ ჩვენს
მაგალითად, ასე გვაქვს რაიმე შედარებით.
ხაზი სამი იწყება მეორე მარყუჟის, რომელშიც ჩვენ iterate მეტი
ყოველ არასორტირებული ელემენტს.
ჩვენ ვიცით, რომ მას შემდეგ, რაც მე iterations, დახარისხებული ნაწილი
ჩვენი სიაში უნდა ჰქონდეს მე ელემენტების იგი წლიდან ყოველი ნაბიჯი
ჯიშები ერთ ელემენტს.
ამიტომ პირველ არასორტირებული ელემენტს უნდა იყოს პოზიცია მე პლუს 1.
On line ოთხი, შევადარებთ მიმდინარე ელემენტი მინიმალური
ელემენტს, რომ ჩვენ ვნახეთ ჯერჯერობით.
თუ მიმდინარე ელემენტს მცირეა მინიმალური
ელემენტს, მაშინ ჩვენ გვახსოვს მიმდინარე ელემენტს როგორც ახალი
მინიმალური on line ხუთი.
ბოლოს, ხაზების ექვსი და შვიდი, ჩვენ სვოპ მინიმალური
ელემენტს პირველი არასორტირებული ელემენტს, რითაც
დასძინა, რომ მას დახარისხებული ნაწილი სიაში.
ერთხელ ჩვენ გვყავს ალგორითმი, მნიშვნელოვანი საკითხის ვთხოვო
საკუთარ თავს, როგორც პროგრამისტები არის რამდენ ხანს საერთოდ რომ მიიღოს?
ჩვენ ვთხოვთ პირველი კითხვა, რამდენი ხანი სჭირდება ამ
ალგორითმი გასაშვებად ყველაზე ცუდ შემთხვევაში?
გავიხსენოთ წარმოვადგენთ ამ გაშვებული
ახლა დიდი O ნოტაცია.
დასადგენად მინიმალური არასორტირებული ელემენტს, ჩვენ
არსებითად ჰქონდა შედარების თითოეულ ელემენტს სია
ყველა სხვა ელემენტს სიაში.
ინტუიციურად, ამ ჟღერს O of n კვადრატში ოპერაცია.
ეძებს ჩვენს pseudocode, ჩვენ ასევე გვაქვს loop წყობილი შიგნით
სხვა loop, რომელიც მართლაც ჟღერს O
საქართველოს N კვადრატში ოპერაცია.
თუმცა გახსოვდეთ, რომ ჩვენ არ უნდა გამოიყურებოდეს მეტი
მთელი სია, როდესაც განმსაზღვრელი მინიმალური არასორტირებული ელემენტს?
ერთხელ ჩვენ ვიცოდით, რომ 4 იყო დახარისხებული, მაგალითად, ჩვენ არ
უნდა შევხედოთ ამას კიდევ ერთხელ.
ასე რომ ჯერ ეს ქვედა ქრონომეტრაჟი?
ჩვენი ჩამონათვალი სიგრძე 6, გვჭირდებოდა, რათა ხუთი
შედარებები პირველად ელემენტს, ოთხი შედარებები ამისთვის
მეორე ელემენტს, და ასე შემდეგ.
ეს იმას ნიშნავს, რომ საერთო რაოდენობის ნაბიჯების თანხა
მთელი რიცხვები 1 დან სიგრძე სიის მინუს 1.
ჩვენ შეგვიძლია წარმოადგენენ ამ summation.
ჩვენ არ წასვლას summations აქ.
მაგრამ აღმოჩნდება, რომ ამ summation უდრის N ჯერ
N მინუს 1 ზე 2.
ან equivalently, N კვადრატში მეტი 2 მინუს N ზე 2.
როდესაც ვსაუბრობთ asymptotic runtime, ამ N კვადრატში ვადა
აპირებს დომინირება ამ N ვადით.
ამიტომ შერჩევას დალაგების არის O of n კვადრატში.
შეგახსენებთ, რომ ჩვენს მაგალითში, შერჩევის დალაგების მაინც საჭიროა
შეამოწმეთ თუ ნომერი, რომელიც უკვე დახარისხებული
საჭირო გადავიდა.
ასე რომ, რაც იმას ნიშნავს, რომ თუ ჩვენ გაიქცა შერჩევის დალაგების მეტი უკვე
დახარისხებული სია, ამას სჭირდება იგივე რაოდენობის ნაბიჯები ისე, როგორც ეს
რომ როდესაც გაშვებული მეტი მთლიანად არასორტირებული სიაში.
ამიტომ შერჩევას დალაგების აქვს საუკეთესო შემთხვევაში შესრულება N კვადრატში,
რომელსაც ჩვენ წარმოვადგენთ ერთად omega N კვადრატში.
და ამით ყველაფერი შერჩევის ჯიშია.
მხოლოდ ერთი ბევრი ალგორითმები შეგვიძლია
გამოყენება დასალაგებლად სიაში.
ჩემი სახელი არის ტომი, და ეს არის cs50.