>> [მუსიკის დაკვრა]
DOUG LLOYD: ყველა უფლება, bubble sort არის ალგორითმი
თქვენ შეგიძლიათ გამოიყენოთ დასალაგებლად კომპლექტი ელემენტები.
მოდით შევხედოთ, თუ როგორ მუშაობს.
>> ასე რომ, ძირითადი იდეა უკან bubble sort არის ეს.
ჩვენ ზოგადად მინდა გადატანა უმაღლესი ღირებული ელემენტები ზოგადად უფლება,
და ქვედა ღირებული ელემენტები ზოგადად მარცხნივ, როგორც ჩვენ მოელოდა.
ჩვენ გვინდა, რომ ქვედა რამ უნდა იყოს დასაწყისში და უმაღლესი რამ
უნდა იყოს ბოლოს.
>> როგორ გავაკეთოთ ეს?
კარგად pseudocode კოდი, შეიძლება ითქვას, რომ, მოდით,
მითითებული swap counter არასამთავრობო ნულოვანი ღირებულება.
ჩვენ დავინახავთ, რატომ ვაკეთებთ, რომ მეორე.
და შემდეგ ჩვენ ვიმეორებ შემდეგი პროცესი სანამ swap counter არის 0,
ან სანამ ჩვენ არ გაცვლებს ყველა.
>> რესეტი swap წინააღმდეგობაში 0 თუ ეს არ არის უკვე 0.
შემდეგ შეხედეთ ყველა მიმდებარე წყვილი ელემენტებს.
თუ ამ ორი ელემენტები არ არის იმისათვის, რომ სვოპ მათ,
და დაამატოთ 1 სვოპ counter.
თუ თქვენ ფიქრი ეს სანამ ვიზუალურად იგი,
შეამჩნია, რომ ეს გადავა ქვედა ღირებული ელემენტები მარცხენა
და უმაღლესი ღირებული ელემენტები მარჯვნივ, ეფექტურად აკეთებს იმას, რაც ჩვენ გვინდა, რომ,
რომელიც გადავა იმ ჯგუფების ელემენტების, რომ გზა.
მოდით ვიზუალურად როგორ ეს შეიძლება გამოიყურებოდეს გამოყენებით ჩვენი მასივი
რომ ჩვენ შეამოწმოთ აღნიშნული ალგორითმები.
ჩვენ გვაქვს დაუხარისხებელი მასივი აქ კიდევ ერთხელ, მიერ მითითებულ ყველა ელემენტები
მიმდინარეობს წითელი.
და მე ჩემს swap counter რომ არ უდრის ნულს ღირებულება.
თვითნებურად აირჩია უარყოფითი 1-- ეს არ არის 0.
შეგახსენებთ, რომ ეს პროცესი სანამ swap counter არის 0.
ამიტომ, მე ჩემს swap counter ზოგიერთი არასამთავრობო ნულოვანი ღირებულება,
რადგან, წინააღმდეგ შემთხვევაში swap counter იქნება 0.
ჩვენ კი არ დაიწყოს პროცესი ალგორითმი.
ასე რომ კიდევ ერთხელ, ნაბიჯები are-- აღადგინოთ swap counter
0, მაშინ შევხედოთ ყველა მიმდებარე წყვილი, და თუ ისინი მწყობრიდან გამოვიდა,
სვოპ მათ, და დაამატოთ 1 რომ swap counter.
ასე რომ დავიწყოთ ამ პროცესში.
ასე რომ, პირველი, რასაც ვაკეთებთ არის ჩვენ მითითებული swap counter 0,
და შემდეგ დავიწყებთ ყოველ მიმდებარე წყვილი.
>> ასე რომ, ჩვენ დავიწყოთ ეძებს 5 და 2.
ჩვენ ვხედავთ, რომ ისინი გარეთ შეკვეთა და ამიტომ ჩვენ სვოპ მათ.
და დავუმატებთ 1 სვოპ counter.
ასე რომ, ახლა ჩვენი swap counter 1, და 2 და 5 უკვე შეცვალა.
ახლა ჩვენ ვიმეორებთ პროცესს კიდევ ერთხელ.
>> ჩვენ შევხედოთ შემდეგი მიმდებარე წყვილი, 5 და 1 ისინი ასევე მწყობრიდან,
ასე რომ, ჩვენ სვოპ მათ და დაამატოთ 1-swap counter.
მაშინ შევხედავთ 5 და 3.
ისინი მწყობრიდან, ამიტომ ჩვენ სვოპ მათ და დავუმატებთ 1 სვოპ counter.
მაშინ შევხედავთ 5 და 6.
ისინი, რათა, ამიტომ ჩვენ არ რეალურად უნდა სვოპ არაფერი ამ დროს.
მაშინ შევხედავთ 6 და 4.
ისინი ასევე მწყობრიდან, ამიტომ ჩვენ სვოპ მათ და დავუმატებთ 1 სვოპ counter.
>> ახლა შეამჩნია, რა მოხდა.
ჩვენ გადავიდა 6 ყველა გზა ბოლომდე.
ასე რომ, შერჩევის დალაგების, თუ თქვენ ჩანს, რომ ვიდეო, რა გავაკეთეთ,
ჩვენ დასრულდა მოძრავი პატარა ელემენტები შენობა
დახარისხებული მასივი, არსებითად, მარცხნიდან მარჯვნივ, პატარა რომ უდიდესი.
იმ შემთხვევაში, თუ bubble sort, თუ ჩვენ შემდეგ ამ კონკრეტულ ალგორითმი,
ჩვენ რეალურად აპირებს უნდა მშენებლობის დახარისხებული array მარჯვნიდან
მარცხნივ, უმსხვილესი to ყველაზე პატარა.
ჩვენ ეფექტურად bubbled 6 უდიდესი მნიშვნელობა, ყველა გზა ბოლომდე.
>> ასე რომ, ახლა ჩვენ შეგვიძლია განვაცხადოთ, რომ ეს არის დახარისხებული,
და მომავალში iterations-- გადის მასივი ერთხელ
ჩვენ არ უნდა განიხილოს 6 უქმნით.
ჩვენ მხოლოდ უნდა განიხილოს არასორტირებული ელემენტები
როდესაც ჩვენ შევხედავთ მიმდებარე წყვილი.
ასე რომ, ჩვენ დასრულდა ერთი გაიაროს bubble sort.
ასე რომ, ახლა ჩვენ დავუბრუნდეთ კითხვას, ვიმეორებ, სანამ swap counter არის 0.
ისე swap counter 4, ამიტომ ჩვენ ვაპირებთ
შევინარჩუნოთ იმეორებს ამ პროცესში კიდევ ერთხელ.
>> ჩვენ ვაპირებთ, რომ აღადგინოთ swap counter 0, და შევხედოთ თითოეული მიმდებარე წყვილი.
ამიტომ, ჩვენ დავიწყებთ 2 და 1 ისინი მწყობრიდან, ამიტომ ჩვენ სვოპ მათ
და დავუმატებთ 1 სვოპ counter.
2 და 3, ისინი მიზნით.
ჩვენ არ გვჭირდება არაფრის.
3 და 5 მიზნით.
ჩვენ არ უნდა გავაკეთოთ არაფერი არსებობს.
>> 5 და 4, ისინი გარეთ იმისათვის, და ამიტომ ჩვენ
უნდა სვოპ მათ და დაამატოთ 1-swap counter.
და ახლა ჩვენ გადავიდა 5, შემდეგი უდიდესი ელემენტი,
ბოლოს არასორტირებული ნაწილი.
ასე რომ, ახლა ჩვენ შეგვიძლია მოვუწოდებთ, რომ ნაწილი დახარისხებული ნაწილი.
>> ახლა თქვენ ეძებს ეკრანზე და ალბათ შემიძლია გითხრათ,
როგორც შემიძლია, რომ მასივი დალაგებულია ახლავე.
მაგრამ ჩვენ არ შეგვიძლია დავამტკიცოთ, რომ ამჟამად.
ჩვენ არ გვაქვს გარანტია რომ ეს დახარისხებული.
მაგრამ ეს არის, სადაც swap counter აპირებს მოვიდეს პიესა.
>> ასე რომ, ჩვენ დასრულდა აკეთებს.
სვოპ counter 2.
ასე რომ, ჩვენ ვაპირებთ გავიმეორო ეს პროცესი კიდევ ერთხელ,
ვიმეორებ, სანამ swap counter არის 0.
რესეტი swap counter 0.
ასე რომ, ჩვენ აღადგინოთ იგი.
>> ახლა შევხედოთ თითოეული მიმდებარე წყვილი.
სწორედ იმისათვის, 1 და 2.
2 და 3 მიზნით.
3 და 4 მიზნით.
ასე რომ, ამ ეტაპზე, შეამჩნია ჩვენ უკვე დასრულდა ეძებს ყოველ მიმდებარე წყვილი,
მაგრამ swap counter კვლავ 0.
>> თუ ჩვენ არ უნდა გადავიდეს ნებისმიერი ელემენტები, მაშინ ისინი
უნდა იყოს იმისათვის, მოძებნა ძალით ამ პროცესში.
ასე რომ, ეფექტურობის სახის, რომ ჩვენ კომპიუტერის მეცნიერები მიყვარს,
არის ახლა ჩვენ შეგვიძლია განვაცხადოთ, მთელი რიგი უნდა
იყოს დახარისხებული, იმიტომ, რომ ჩვენ არ უნდა სვოპ ნებისმიერი ელემენტები.
ეს არის საკმაოდ ლამაზი.
>> ასე რომ, რა უარეს შემთხვევაში სცენარი ბუშტი დალაგება?
უარეს შემთხვევაში მასივი სრულიად საპირისპირო მიზნით,
და ამიტომ ჩვენ უნდა ბუშტი თითოეულ ერთი დიდი ელემენტები ყველა
გზა მასშტაბით მასივი.
ჩვენ ეფექტურად ასევე უნდა bubble ყველა პატარა ელემენტები უკან
ყველა გზა მასშტაბით მასივი, ძალიან.
ასე რომ, თითოეული N ელემენტები უნდა გადავიდეს მთელი მეორე n ელემენტებს.
ასე რომ, უარეს შემთხვევაში.
საუკეთესო შემთხვევაში სცენარი, თუმცა, ეს არის
ოდნავ განსხვავებული შერჩევა ერთგვარი.
მასივი უკვე დალაგებულია, როდესაც ჩვენ წავიდეთ.
ჩვენ არ გვაქვს რაიმე სვოპების პირველ უღელტეხილზე.
ასე რომ, ჩვენ შეიძლება უნდა გამოიყურებოდეს განთავსებულია ნაკლები ელემენტები, არა?
ჩვენ არ უნდა გავიმეოროთ ეს დამუშავებას ნომერი ჯერ მეტი.
>> ასე რომ, რას ნიშნავს ეს?
ასე რომ, რა არის ყველაზე უარესი სცენარი ამისთვის bubble sort, და რა არის
საუკეთესო სცენარით ბუშტი დალაგება?
ხომ იცი, ეს?
უარეს შემთხვევაში თქვენ უნდა iterate მთელი n ელემენტებს N ჯერ.
ასე რომ, უარეს შემთხვევაში არის n კვადრატში.
>> იმ შემთხვევაში, თუ მასივი მშვენივრად დახარისხებული, თუმცა, თქვენ მხოლოდ
უნდა შევხედოთ თითოეული ელემენტები ერთხელ.
და თუ swap counter კვლავ 0, შეიძლება ითქვას, ამ მასივი დალაგებულია.
ასე რომ, საუკეთესო შემთხვევაში, ეს არის რეალურად უკეთესი არჩევანი
დალაგება ის omega of ო.
>> მე Doug Lloyd.
ეს არის CS50.