ბუშტუკების დალაგება შერჩევით დალაგების წინააღმდეგ
Bubble Sort არის დახარისხების ალგორითმი, რომელიც მოქმედებს სიის განმეორებით დასალაგებლად, მეზობელ ელემენტების წყვილების შედარებისას. თუ ელემენტების წყვილი არასწორი თანმიმდევრობითაა, ისინი იცვლებიან სწორი თანმიმდევრობით დასაყენებლად. ეს ტრავერსი მეორდება მანამ, სანამ შემდგომი გაცვლა არ არის საჭირო. Selection Sort ასევე არის დახარისხების ალგორითმი, რომელიც იწყება სიაში მინიმალური ელემენტის მოძიებით და მისი პირველი ელემენტით შეცვლით. ეს პროცესი მეორდება სიის დარჩენილი ნაწილისთვის გაცვლილი ელემენტების თანმიმდევრობით მოთავსებით.
რა არის Bubble Sort?
Bubble Sort არის დახარისხების ალგორითმი, რომელიც მოქმედებს სიის განმეორებით დასალაგებლად, მეზობელ ელემენტების წყვილების შედარებისას. თუ ელემენტების წყვილი არასწორი თანმიმდევრობითაა, ისინი იცვლებიან სწორი თანმიმდევრობით დასაყენებლად. ეს გადაკვეთა მეორდება მანამ, სანამ შემდგომი გაცვლა არ არის საჭირო (რაც ნიშნავს, რომ სია დალაგებულია). მას შემდეგ, რაც სიაში უფრო მცირე ელემენტები ჩნდება ზედა ზედაპირზე ბუშტის გამოსვლისას, მას მიენიჭა სახელი ბუშტის დალაგება. ბუშტების დალაგება არის ძალიან მარტივი დახარისხების ალგორითმი, მაგრამ მას აქვს O(n2) სირთულის საშუალო სირთულის დრო სიის n ელემენტით დახარისხებისას. ამის გამო, ბუშტების დალაგება არ არის შესაფერისი ელემენტების დიდი რაოდენობით სიების დასახარისხებლად. მაგრამ მისი სიმარტივის გამო, ბუშტების დალაგება ისწავლება ალგორითმების შესავლისას.
რა არის შერჩევის დახარისხება?
შერჩევის დალაგება ასევე არის სხვა დახარისხების ალგორითმი, რომელიც იწყება სიაში მინიმალური ელემენტის მოძიებით და მისი პირველი ელემენტით შეცვლით.შემდეგ მინიმალური ელემენტი იპოვება სიის დარჩენილი ნაწილიდან (მეორე ელემენტიდან სიის ბოლო ელემენტამდე) და იცვლება მეორე ელემენტთან. ეს პროცესი მეორდება სიის დარჩენილი ნაწილისთვის გაცვლილი ელემენტების თანმიმდევრობით მოთავსებით. ასე რომ, შერჩევის დალაგებისას, ალგორითმის ნებისმიერ საფეხურზე, სია იყოფა ორ ნაწილად, სადაც ერთი ნაწილი შეიცავს დახარისხებულ ელემენტებს, ხოლო მეორე ნაწილი შეიცავს დაუხარისხებელ ელემენტებს. როგორც ალგორითმი გრძელდება, დალაგებული სია იზრდება მარცხნიდან მარჯვნივ. შერჩევის დალაგებას ასევე აქვს O(n2) საქმის დროის საშუალო სირთულე. ამიტომ ის ასევე არ არის შესაფერისი დიდი სიების დასალაგებლად.
რა განსხვავებაა Bubble Sort-სა და Selection Sort-ს შორის?
მიუხედავად იმისა, რომ როგორც ბუშტების დალაგების, ისე შერჩევის დალაგების ალგორითმები საშუალო შემთხვევების დროის სირთულეა O(n2), ბუშტების დალაგება თითქმის ყველა დროში აჭარბებს შერჩევის დალაგებას. ეს გამოწვეულია ორი ალგორითმისთვის საჭირო სვოპების რაოდენობით (ბუშტუკების დალაგება საჭიროებს მეტ გაცვლას).მაგრამ ბუშტების დალაგების სიმარტივის გამო, მისი კოდის ზომა ძალიან მცირეა. სტაბილურობა კიდევ ერთი განსხვავებაა ამ ორ ალგორითმში. სტაბილური დახარისხების ალგორითმი, არის დახარისხების ალგორითმი, რომელიც ინარჩუნებს ჩანაწერების წესრიგს, თუ სია შეიცავს თანაბარი მნიშვნელობის ელემენტებს. ამ თვალსაზრისით, შერჩევის დალაგება არ არის სტაბილური ალგორითმი, ხოლო ბუშტების დალაგება არის სტაბილური ალგორითმი.
