ბუშტუკების დალაგება vs ჩასმის სორტირება
Bubble Sort არის დახარისხების ალგორითმი, რომელიც მოქმედებს სიის განმეორებით დასალაგებლად, მეზობელ ელემენტების წყვილების შედარებისას. თუ ელემენტების წყვილი არასწორი თანმიმდევრობითაა, ისინი იცვლებიან სწორი თანმიმდევრობით დასაყენებლად. ეს ტრავერსი მეორდება მანამ, სანამ შემდგომი გაცვლა არ არის საჭირო. Insertion sort ასევე არის დახარისხების ალგორითმი, რომელიც მოქმედებს შეყვანის სიაში ელემენტის ჩასმით სწორ პოზიციაზე უკვე დალაგებულ სიაში. ეს პროცესი არაერთხელ გამოიყენება სიის დახარისხებამდე.
რა არის Bubble Sort?
Bubble Sort არის დახარისხების ალგორითმი, რომელიც მოქმედებს სიის განმეორებით დასალაგებლად, მეზობელ ელემენტების წყვილების შედარებისას. თუ ელემენტების წყვილი არასწორი თანმიმდევრობითაა, ისინი იცვლებიან სწორი თანმიმდევრობით დასაყენებლად. ეს გადაკვეთა მეორდება მანამ, სანამ შემდგომი გაცვლა არ არის საჭირო (რაც ნიშნავს, რომ სია დალაგებულია). მას შემდეგ, რაც სიაში უფრო მცირე ელემენტები ჩნდება ზედა ზედაპირზე ბუშტის გამოსვლისას, მას მიენიჭა სახელი ბუშტის დალაგება. ბუშტების დალაგება არის ძალიან მარტივი დახარისხების ალგორითმი, მაგრამ მას აქვს O(n2) სირთულის საშუალო სირთულის დრო სიის n ელემენტით დახარისხებისას. ამის გამო, ბუშტების დალაგება არ არის შესაფერისი ელემენტების დიდი რაოდენობით სიების დასახარისხებლად. მაგრამ მისი სიმარტივის გამო, ბუშტების დალაგება ისწავლება ალგორითმების შესავლისას.
რა არის Insertion Sort?
ჩასმის დალაგება არის სხვა დახარისხების ალგორითმი, რომელიც მოქმედებს შეყვანის სიაში ელემენტის ჩასმით სიაში სწორ პოზიციაზე (რომელიც უკვე დალაგებულია).ეს პროცესი არაერთხელ გამოიყენება სიის დახარისხებამდე. ჩასმული დალაგებისას დახარისხება ხდება ადგილზე. ამიტომ ალგორითმის მეორადი გამეორების შემდეგ, სიაში პირველი i+1 ჩანაწერები დალაგდება, ხოლო დანარჩენი სიის დაუხარისხებელი. ყოველი გამეორებისას, სიის დაუხარისხებელი ნაწილის პირველი ელემენტი იქნება აღებული და ჩასმული სიის დახარისხებულ განყოფილებაში სწორ ადგილას. ჩასმის დალაგებას აქვს O(n2) საქმის დროის საშუალო სირთულე. ამის გამო, ჩასმის დალაგება ასევე არ არის შესაფერისი დიდი სიების დასალაგებლად.
რა განსხვავებაა Bubble Sort-სა და Insertion Sort-ს შორის?
მიუხედავად იმისა, რომ ორივე ბუშტის დალაგების და ჩასმის დალაგების ალგორითმს აქვს O(n2) საშუალო შემთხვევათა დროის სირთულე, ბუშტების დალაგება თითქმის ყოველთვის აღემატება ჩასმის დალაგებას. ეს გამოწვეულია ორი ალგორითმისთვის საჭირო სვოპების რაოდენობით (ბუშტუკების დალაგება საჭიროებს მეტ გაცვლას). მაგრამ ბუშტების დალაგების სიმარტივის გამო, მისი კოდის ზომა ძალიან მცირეა.ასევე არის ჩასმული დალაგების ვარიანტი, რომელსაც ეწოდება shell sort, რომელსაც აქვს O(n3/2) დროის სირთულე, რაც მის პრაქტიკულად გამოყენების საშუალებას იძლევა. გარდა ამისა, ჩასმის დალაგება ძალიან ეფექტურია „თითქმის დალაგებული“სიების დასალაგებლად, ბუშტების დალაგებასთან შედარებით.
