[Powered by Google Translate] [Bubble დასალაგებლად] [JACKSON STEINKAMP ჰარვარდის უნივერსიტეტი] [ეს არის CS50. CS50TV] Bubble დალაგების არის მაგალითი დახარისხება ალგორითმი - რომ არის, პროცედურა დახარისხება კომპლექტი ელემენტების აღმავალი ან დაღმავალი შეკვეთ. მაგალითად, თუ თქვენ სურდა დასალაგებლად მასივი შემდგარი ნომრები [3, 5, 2, 9], სწორი განხორციელება Bubble დალაგების დაბრუნდნენ დახარისხებული array [2, 3, 5, 9] აღმავალი შეკვეთა. ახლა, მე ვაპირებ ახსნას წელს pseudocode როგორ ალგორითმი მუშაობს. 

ვთქვათ ჩვენ დახარისხება სიაში 5 რიცხვებით - 3, 2, 9, 6, და 5. ალგორითმი იწყებს მიერ ეძებს პირველი ორი ელემენტები, 3 და 2, და შემოწმების თუ ისინი მწყობრიდან ნათესავი ერთმანეთს. ისინი - 3 მეტია 2. უნდა იყოს აღმავალი შეკვეთა, ისინი უნდა იყოს პირიქით. ასე რომ, ჩვენ სვოპ მათ. ახლა სია ასე გამოიყურება: [2, 3, 9, 6, 5]. 

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

ამიტომ, ჩვენ უნდა სვოპ მათ, რადგან 9 მეტია 6. და ბოლოს, ჩვენ შევხედოთ ბოლო ორი რიცხვებით, 9 და 5. ისინი მწყობრიდან გამოვიდა, ასე რომ მათ უნდა swapped. შემდეგ პირველი სრულ გადის სია, იგი ასე გამოიყურება: [2, 3, 6, 5, 9]. ნორმალური. თითქმის დახარისხებული. მაგრამ ჩვენ გვჭირდება აწარმოებს მეშვეობით სიაში კვლავ მიიღოს იგი მთლიანად დახარისხებული. ორი ნაკლებია, ვიდრე 3, ასე რომ ჩვენ არ სვოპ მათ. 

სამი ნაკლებია, ვიდრე 6, ამიტომ ჩვენ არ სვოპ მათ. ექვსი მეტია 5. ჩვენ swapped. ექვსი ნაკლებია, ვიდრე 9. ჩვენ არ სვოპ. შემდეგ მეორე გადის, ის ასე გამოიყურება: [2, 3, 5, 6, 9]. Perfect. ახლა, მოდით, დაწერეთ ის pseudocode. ძირითადად, თითოეული ელემენტი სია, ჩვენ უნდა შევხედოთ ამას და ელემენტს პირდაპირ თავისი უფლება. თუ ისინი მწყობრიდან ნათესავი ერთმანეთს - ეს არის, თუ ელემენტს მარცხენა მეტია ერთი მარჯვენა - ჩვენ უნდა სვოპ ორი ელემენტები. 

ჩვენ ამას ვაკეთებთ, ყოველ ელემენტს სია, და ჩვენ კიდევ ერთი გადის. ახლა ჩვენ უბრალოდ უნდა გავაკეთოთ უღელტეხილზე გზით საკმარისი ჯერ რათა უზრუნველყოს სია სრულად, ჯეროვნად დახარისხებული. მაგრამ რამდენჯერ გვაქვს შემოვლითი გზით სია გარანტიას, რომ ჩვენ გავაკეთეთ? ისე, უარესი სცენარით არის თუ გვაქვს სრულიად უკან სიაში. მაშინ სჭირდება ხმების გაივლის-throughs ტოლი რაოდენობის ელემენტების N-1. თუ ეს არ აქვს აზრი ინტუიციურად, ვფიქრობ მარტივი შემთხვევაში - სია [2, 1]. 

ეს აპირებს მიიღოს ერთი უღელტეხილის გზით დასალაგებლად სწორად. [3, 2, 1] - უარეს შემთხვევაში არის, რომ 3 ელემენტები დალაგებულია უკან, ის აპირებს 2 iterations დასალაგებლად. შემდეგ ერთი iteration, ეს [2, 1, 3]. მეორე შემოსავალი დახარისხებული array [1, 2, 3]. ასე რომ თქვენ იცით, თქვენ არასოდეს არ გავლა მასივი, ზოგადად, ზე მეტი N-1 ჯერ, სადაც n რაოდენობის ელემენტების მასივი. ეს მოუწოდა Bubble დალაგების რადგან უმსხვილესი ელემენტები ტენდენცია 'ბუშტი-up' მარჯვნივ საკმაოდ სწრაფად. ფაქტობრივად, ეს ალგორითმი აქვს ძალიან საინტერესო ქცევა. 

შემდეგ მ iterations მთელი მასივი, rightmost m ელემენტები გარანტირებული უნდა იყოს დახარისხებული მათ სწორი ადგილი. თუ გვინდა, რომ ამ თავს, ჩვენ შეგვიძლია ვცდილობთ იგი მთლიანად უკან სიაში [9, 6, 5, 3, 2]. შემდეგ ერთი გადის მთელი სია, [ხმა წერის] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] rightmost ელემენტს 9 მის სათანადო ადგილი. შემდეგ მეორედ შემოჭრის გზით, 6 ექნება "bubbled-up 'to მეორე rightmost ადგილი. ორი ელემენტები, მარჯვნივ - 6 და 9 - იქნება მათი სწორი ადგილებში შემდეგ პირველ ორ უღელტეხილზე-throughs. 

ასე რომ, როგორ შეგვიძლია გამოვიყენოთ ეს ოპტიმიზაციის ალგორითმი? ისე, ერთი iteration მეშვეობით მასივი ჩვენ არ რეალურად უნდა შეამოწმოთ rightmost ელემენტს რადგან ჩვენ ვიცით, ეს დახარისხებული. შემდეგ ორი iterations, ჩვენ ვიცით, rightmost ორი ელემენტია ადგილზე. ასე რომ, ზოგადად, შემდეგ K iterations მეშვეობით სრული მასივი, შემოწმების ბოლო K ელემენტები არის გადაჭარბებული, რადგან ჩვენ ვიცით, ისინი სწორი საიდან უკვე. 

ასე რომ, თუ თქვენ დახარისხება მასივი N ელემენტები, პირველ iteration - you'll უნდა დასალაგებლად ყველა ელემენტი - პირველ N-0. მეორე iteration, თქვენ უნდა შევხედოთ ყველა ელემენტები, მაგრამ ბოლო - პირველი n-1. კიდევ ერთი ოპტიმიზაცია შეიძლება იყოს, რათა შეამოწმოთ, თუ სიაში უკვე დახარისხებული ყოველი iteration. თუ ეს უკვე დახარისხებული, ჩვენ არ გვჭირდება რაიმე უფრო iterations მეშვეობით სიაში. როგორ შეგვიძლია ამის გაკეთება? ისე, თუ ჩვენ არ მიიღოს ნებისმიერი სვოპების on უღელტეხილზე გზით სიის, ნათელია, რომ სიაში უკვე დახარისხებული რადგან ჩვენ ვერ სვოპ არაფერი. ამიტომ, ჩვენ ნამდვილად არ უნდა დასალაგებლად ერთხელ. 

ალბათ თქვენ ვერ ვრთავ დროშა ცვლადში "არ დახარისხებული 'to ცრუ და შეცვალოს იგი ჭეშმარიტია თუ თქვენ უნდა სვოპ ნებისმიერი ელემენტების ერთი iteration მეშვეობით მასივი. ან მსგავსი, მიიღოს counter დათვლა რამდენი სვოპების თქვენ გააკეთებთ ნებისმიერ მოცემულ iteration. დასასრულს iteration, თუ თქვენ არ სვოპ ნებისმიერი ელემენტები, თქვენ იცით სიაში უკვე დახარისხებული და თქვენ კეთდება. Bubble დალაგების, ისევე როგორც სხვა დახარისხება ალგორითმები, შეიძლება იყოს tweaked მუშაობა ნებისმიერი ელემენტი, რომლებსაც აქვთ შეკვეთით მეთოდი. 

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

Bubble დალაგების არის არ ნიშნავს ძალიან ეფექტური ან სწრაფი დახარისხება ალგორითმი. მისი უარესი Runtime არის დიდი O of n ² იმიტომ, რომ თქვენ უნდა გააკეთოთ N iterations მეშვეობით სია შემოწმების ყველა N ელემენტების ყოველ უღელტეხილზე გზით, nxn = n ². ეს გაუშვათ დროის იმას ნიშნავს, რომ, როგორც რაოდენობის ელემენტები თქვენ დახარისხება იზრდება, პერსპექტივაში დრო იზრდება quadratically. 

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