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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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