>> MARK GROZEN-SMITH: Hi, მე ჩანაწერები Grozen-Smith, და ეს არის Quicksort.
ისევე როგორც ჩანართი სახის და ბუშტი დალაგების, Quicksort არის ალგორითმი
დახარისხება სიაში ან მასივი რამ.
სიმარტივის, მოდით ვივარაუდოთ, რომ იმ სიტუაცია უბრალოდ რიცხვებით, მაგრამ
ვიცი, რომ Quicksort სამუშაოები მეტი, ვიდრე უბრალოდ ნომრები.
Quickstart არის ცოტა უფრო რთული გარდა ჩასმის ან ბუშტი, მაგრამ ეს
ასევე ბევრად უფრო ეფექტური ხშირ შემთხვევაში.
დაველოდოთ მეორე.
მან, უბრალოდ, ვამბობთ "ყველაზე შემთხვევაში, "არა" ყველა "?
საინტერესოა, არა.
არა ყველა შემთხვევაში ერთნაირია.
არ აღელვებს ეს დეტალი თუ არ მინახავს დიდი O ნოტაცია არ არის, მაგრამ
Quicksort არის O (N კვადრატი) ალგორითმი უარეს შემთხვევაში, ისევე, როგორც
ჩასმის ან bubble sort.
თუმცა, ეს, როგორც წესი, მოქმედებს, ბევრად უფრო ისევე როგორც ძველი ანალოგური m ალგორითმი.
რატომ?
ჩვენ დავუბრუნდეთ მოგვიანებით.
მაგრამ ახლა, მოდით უბრალოდ ვისწავლოთ როგორ Quicksort მუშაობს.
>> მოდით გავლა Quicksorting ამ მასივი რიცხვებით ეხლა პატარა
რომ ყველაზე დიდი.
აქ ჩვენ გვაქვს რიცხვებით 6, 5, 1, 3, 8, 4, 7, 9, და 2.
პირველი, ჩვენ აირჩიოთ საბოლოო ელემენტს ამ მასივი - ამ შემთხვევაში, ორი -
და მოვუწოდებთ, რომ "pivot". შემდეგი, ჩვენ დაიწყოს შევხედოთ ორი რამ -
ერთი, ყველაზე დაბალი მაჩვენებელი, რომელიც მე ეხება როგორც დარჩენის უფლება
კედელი, და, ორი, leftmost ელემენტს, რომელიც მე მოვუწოდებ "მიმდინარე
ელემენტს. "ჩვენ ვაპირებთ გავაკეთოთ არის შეხედეთ ყველა სხვა ელემენტები, სხვა
ვიდრე მდებარეობა, და ამით ყველა ელემენტები ნაკლებია pivot რომ
დარჩა კედელზე და ყველა იმ აღემატება pivot რომ
მარჯვენა კედელზე.
მაშინ, საბოლოოდ, ჩვენ ჩამოაგდეს pivot უფლება, რომ კედელი დააყენოს ის შორის
ყველა ნომრები პატარა, ვიდრე ეს და ყველა რიცხვი დიდია.
>> მოდით გავაკეთოთ ეს.
აიღეთ 2, დააყენა კედლის საათზე დასაწყისია, და მოვუწოდებთ 6 "მიმდინარე
ელემენტს. "ამიტომ, ჩვენ გვინდა, რომ შევხედოთ ჩვენი დღევანდელი ელემენტს, 6.
და რადგან აღემატება 2, დავტოვებთ იქ
მარჯვენა კედელზე.
ამის შემდეგ, ჩვენ გადაადგილება შევხედოთ 5, როგორც ჩვენი მიმდინარე ელემენტს და ვხედავთ, რომ ეს
, კიდევ ერთხელ, უფრო დიდი, ვიდრე pivot, ამიტომ ჩვენ დატოვება, სადაც ის არის მარჯვენა
მხარეს კედელი.
ჩვენ გადაადგილება.
ჩვენი დღევანდელი ელემენტი ახლა 1 და - oh.
ეს არის სხვადასხვა არის.
მიმდინარე ელემენტს არის პატარა, ვიდრე pivot, ასე რომ გსურთ განათავსოთ
მარცხნივ კედელზე.
ამისათვის მოდით უბრალოდ გადართოთ მიმდინარე ელემენტს ყველაზე დაბალი მაჩვენებელი
სხდომაზე მხოლოდ მარჯვენა კედელი.
ახლა ჩვენ გადაადგილება კედლის ერთი ინდექსი ასე რომ 1 არის მარცხენა
მხარეს კედლის ახლა.
>> დაველოდოთ.
მე უბრალოდ აირია ელემენტების მარჯვენა მხარეს კედელზე, არ ვარ?
არ ინერვიულოთ.
ეს ჯარიმა.
ერთადერთი, რაც ჩვენ აღელვებს ახლა ის არის, რომ ყველა ამ ელემენტების
მარჯვენა კედელზე არის დიდი ვიდრე pivot.
არ ფაქტობრივი მიზნით აიღო არავის გაუკეთებია.
>> ახლა, უკან დახარისხება.
ასე რომ, ჩვენ გავაგრძელებთ ეძებს დანარჩენი ელემენტები.
და ამ შემთხვევაში, ჩვენ ვხედავთ, რომ არსებობს არც ერთ სხვა ელემენტს ნაკლები
pivot, ამიტომ დატოვეთ ყველა მარჯვენა მხარეს კედელი.
საბოლოოდ, ჩვენ კიდევ მიმდინარე ელემენტს და ვხედავთ, რომ ეს არის pivot.
ახლა, რაც იმას ნიშნავს, რომ ჩვენ გვაქვს ორი განყოფილებები მასივი, პირველი ყოფნა
მცირე pivot და მარცხენა მხარეს კედლის და მეორე ყოფნა
აღემატება pivot რომ მარჯვენა მხარეს კედელი.
ჩვენ გვინდა, რომ დააყენა pivot ელემენტს შორის ორი, და შემდეგ გვეცოდინება
რომ pivot არის მისი უფლება, საბოლოო დახარისხებული ადგილას.
ასე რომ, ჩვენ გადავიდეს პირველ ელემენტს მარჯვენა მხარეს კედლის pivot,
და ჩვენ ვიცით, pivot მიერ მისი სწორი პოზიცია.
>> ჩვენ მაშინ ვიმეორებ ეს პროცესი subarrays მარცხენა და მარჯვენა pivot.
გასული subarray არის მხოლოდ ერთი ელემენტის ხანგრძლივი, ჩვენ ვიცით, რომ უკვე
დახარისხებული, რადგან როგორ შეიძლება იყოს out of შეკვეთა თუ თქვენ მხოლოდ ერთი ელემენტია?
რომ მარჯვენა მხარეს subarray, ჩვენ ვხედავთ, რომ pivot 5 და კედლის
უბრალოდ დარჩა 6.
და მიმდინარე ელემენტს ასევე იწყება, როგორც 6.
ასე რომ, 6 მეტია 5.
ჩვენ დატოვება, სადაც ის არის მარჯვენა მხარეს კედელი.
ახლა, მოძრავი, 3 ნაკლებია 5.
ასე რომ, ჩვენ გადახვიდეთ იგი პირველ ელემენტს უბრალოდ უფლება კედლის.
ახლა, მე გადავიდა კედელზე ერთი.
ახლა, მოძრავი 8.
8 აღემატება 5, და ამიტომ ჩვენ დატოვოს იგი.
4 ნაკლებია, ვიდრე 5, ამიტომ ჩვენ ჩართოთ იგი.
და.
>> ყოველ ჯერზე ჩვენ ვიმეორებ პროცესში მარცხენა და მარჯვენა მხარეს მასივი. ჩვენ
აირჩიეთ pivot და გავაკეთოთ შედარებები და შექმნა მეორე დონის მარცხენა და
მარჯვენა subarrays.
ამ რეკურსიული ზარი გაგრძელდება ჩვენ მივაღწიოთ ბოლოს, როდესაც ჩვენ
დაყოფილია საერთო მასივი შევიდა უბრალოდ subarrays სიგრძე 1.
იქიდან, ჩვენ ვიცით მასივი დალაგებულია რადგან ყველა ელემენტს აქვს, რომ
რაღაც მომენტში, უკვე pivot.
სხვა სიტყვებით, ყოველ ელემენტს, ყველა ციფრები, რომ მარცხნივ ნაკლებმნიშვნელოვანი
ღირებულებები და ყველა ნომრები უფლება აქვს უფრო დიდი ღირებულებები.
>> ეს მეთოდი მუშაობს ძალიან კარგად, თუ ღირებულება pivot არჩეული
დაახლოებით შუა სპექტრი სიაში ღირებულებებს.
ეს ნიშნავს, რომ მას შემდეგ, რაც ჩვენ გადაადგილება ელემენტები გარშემო, იქ იმდენი
ელემენტები მარცხენა pivot როგორც არსებობს უფლება.
და გათიშე და დაპყრობა ბუნების Quicksort ალგორითმი შემდეგ გადაიყვანეს
სრული უპირატესობა.
ეს ქმნის runtime of O (n log n,) n იმიტომ, რომ ჩვენ უნდა გავაკეთოთ n მინუს 1
შედარება ყოველი თაობის და log n რადგან ჩვენ უნდა გავყოთ სია
შესვლა N ჯერ.
თუმცა, უარეს შემთხვევაში, ამ ალგორითმი შეიძლება რეალურად იყოს O (n
კვადრატი.) დავუშვათ, რომ თითოეული თაობა, pivot უბრალოდ ისე ხდება, რომ იყოს
პატარა და ყველაზე დიდი ნომერი ჩვენ დახარისხება.
ეს იმას ნიშნავს, ჩაშლის სია n-ჯერ, ხოლო მიღების n მინუს 1
შედარება თითოეული დრო.
ამდენად, o of n კვადრატში.
>> როგორ შეგვიძლია გაუმჯობესება მეთოდი?
ერთი კარგი გზა, რათა გააუმჯობესოს მეთოდი მოჭრა ალბათობა, რომ
runtime ოდესმე რეალურად o of n კვადრატში.
დამახსოვრება ეს უარესი, უარეს შემთხვევაში სცენარი მხოლოდ მაშინ მოხდება, როცა
pivot არჩეული ყოველთვის უმაღლესი ან დაბალი ღირებულების მასივი.
იმისათვის, რათა ეს ნაკლებად სავარაუდოა, რომ მოხდეს, ჩვენ შეგვიძლია მოვძებნოთ pivot მიერ
არჩევის მრავალჯერადი ელემენტები და აღების საშუალო ღირებულება.
>> ჩემი სახელია Mark Grozen-Smith, და ეს არის CS50.
>> სიმარტივის, მოდით ვივარაუდოთ, რომ იმ სიტუაცია უბრალოდ რიცხვებით, მაგრამ
ვიცი, რომ Quicksert -
Quicksert?
უკაცრავად.
>> აქ ჩვენ გვაქვს რიცხვებით 6, 5, 1, 3, 8, 4, 9.
>> დინამიკები 1: მართლა?
>> დინამიკები 2: არ მთავრდება.
>> დინამიკები 1: მართლა?