რომელი სორტირების ალგორითმი გამოიყენოთ და როდის
27.05.2022
პროგრამირება
ბინარული ძებნა გამოიყენება მასივის ეფექტურად გასავლელად, მაგრამ ბინარული ძიება მუშაობს მხოლოდ მაშინ, როდესაც მასივი სორტირებულია.
მაშინ, როგორ მოხდება მნიშვნელობების მასივის სორტირება?
მოკლე პასუხი: არსებობს მრავალი სახის სორტირება, და გადაწყვეტილების მიღება, თუ რომელი მეთოდი გამოვიყენოთ, დამოკიდებულია სიტუაციაზე.
უფრო დეტალურად რომ გავიგოთ, ჩვენ უნდა შევხედოთ სორტრების სამ სხვადასხვა ალგორითმს:
- შეყვანითი სორტირება
- შერწყმითი სორტირება
- სელექციური სორტირება
სელექციური სორტირება
"სელექციური სორტირება" - ყველაზე საბაზისო ტიპი, ალგორითმი განმეორებითად პოულობს უმცირეს მნიშვნელობას დაუხარისხებელი ქვემასივიდან და გადააქვს იგი სორტირებულ ქვემასივში, მასივის დასაწყისში.
ქვემასივი არის მასივის ნაწილი. იქნება ორი ქვემასივი: სორტირებული ნაწილი და დარჩენილი არასორტირებული ნაწილი.
ქვემოთ მოცემულია მასივის მაგალითი:
თავდაპირველად, ყველაზე მცირე მნიშვნელობა დაყენებულია საწყისი ინდექსის მნიშვნელობაზე („5“). როდესაც მთელი მასივი გაივლება და აღმოჩნდება უმცირესი მნიშვნელობა („1“), შეცვალეთ უმცირესი მნიშვნელობა საწყისი ინდექსის მნიშვნელობით. გაიმეორეთ პროცესი მომდევნო მნიშვნელობისთვის და გაიმეორეთ მანამ, სანამ არ გადაკვეთთ მთელ მასივს.
გაითვალისწინეთ! როდესაც რაიმე სწრაფად გჭირდებათ, სელექციური სორტირება მარტივი, თუმცა არც ისე ეფექტური არჩევანია.
შეყვანითი სორტირება
მეორე მხრივ, შეყვანითი სორტირება პოულობს მომდევნო მნიშვნელობებს და ახარისხებს მათ. ასე რომ, თქვენ უნდა გამოიყენოთ შეყვანითი სორტირება დაუხარისხებელი მასივის უმცირესი რიცხვიდან უდიდეს რიცხვამდე გადასაწყობად.
წარმოიდგინეთ, რომ სათითაოდ გირიგებენ კარტს. კარტების ორგანიზებაში დასახმარებლად, თავიდანვე იწყებთ დარიგებული კარტების სორტირებას ყველაზე მცირე მნიშვნელობით.
თქვენი ამჟამინდელი დაუხარისხებელი ხელის გათვალისწინებით, როგორ დაიწყებდით თქვენი კარტების დახარისხებას? შეყვანითი სორტირება გავს იმას, თუ როგორც დაახარისხებდით კარტის ამ ხელს.
დაიწყეთ პირველი კარტით ხელში. მის მარცხნივ კარტი არ არის, ამიტომ ის რჩება. მეორე ბარათი ახლა არის მთავარი და დადგება მის მარცხნივ მყოფ კარტთან. ვინაიდან 4 მეტია, 4 გადადის ერთი პოზიციით წინ.
ისევ და ისევ, განსხვავება აქ არის ის, რომ სელექციური სორტირება მუდმივად პოულობს უმცირეს მნიშვნელობას, ხოლო შეყვანითი სორტირება პოულობს შემდგომ მნიშვნელობებს და ახარისხებს მათ.
განთავისუფლდი ბანალური საგანმანათლებლო სისტემისგან, დაიწყე დიზაინის სწავლა სრულიად ახალი მეთოდებით და გახდი წარმატებული სტეპერი!
შერწყმითი სორტირება
და ბოლოს, შერწყმითი სორტირება არის ‘დაყავი და იბატონე’ პრინციპის ალგორითმი, რომელიც აგრძელებს მასივის ნახევრებად დაყოფას მანამ, სანამ გაყოფილი ქვემასივი არ შედგება ერთი ელემენტისგან. იქიდან, ის აერთიანებს ნახევრებს ისევ ერთად, ხოლო შერწყმისას ახდენს მნიშვნელობების სორტირებას.
ამ შედეგის მისაღწევად, თქვენ გჭირდებათ რეკურსია, რომელიც არის პროგრამირების ტექნიკა, რომელშიც მეთოდი თავის თავს იძახებს. ის ხშირად გამოიყენება, როდესაც პრობლემის გადაჭრა შესაძლებელია ქვეპრობლემებად დაყოფით, რომლებიც თავის მხრივ იყენებენ იმავე ტექნიკას მათ გადასაჭრელად.
საბაზისო ქეისი აბრუნებს მნიშვნელობას რეკურსიული ზომების გამოძახების გარეშე. მეთოდი, რომელიც თავის თავს იძახებს, არ გააგრძელებს მისი დანარჩენი კოდის გაშვებას მანამ, სანამ გამოძახებული მეთოდი არ დააბრუნებს მნიშვნელობას.
მაგალითად, ვთქვათ, რომ წვეულებაზე გსურთ პიცა შეუკვეთოთ თქვენთვის და თქვენი მეგობრებისთვის. მაგრამ თქვენ შეუკვეთავთ პიცას მხოლოდ იმ შემთხვევაში, თუ თქვენი მეგობარი შეჭამს პიცას და თქვენი მეგობარი შეჭამს პიცას მხოლოდ იმ შემთხვევაში, თუ მისი მეგობარი შეჭამს პიცას. ეს გრძელდება მანამ, სანამ ერთი მეგობარი არ იტყვის, რომ საკმარისია და უბრალოდ იტყვის „კარგი, შევუკვეთოთ“. ეს "კარგი" შემდეგ გადაეცემა მეგობრიდან მეგობარს და მოვა თქვენამდე.
ინფორმაციის ეს ნაკადი ჰგავს კოდში რეკურსიის მუშაობას. რეკურსიული მეთოდი აგრძელებს თავის გამოძახებას, სანამ პასუხი არ მოიძებნება. თითოეული ადამიანი წარმოადგენს ერთ გამოძახებას საკუთარი თავისთვის. მეთოდი განაგრძობს თავის გამოძახებას მანამ, სანამ საბაზისო ქეისი არ მიიღწევა. ამ მაგალითში, საბაზისო ქეისი არის პირველი "კარგი!" და უბრუნდება პირველ გამოძახებას.
როდესაც გჭირდებათ სტაბილური სორტირება ან გჭირდებათ მონაცემთა დიდი ნაკადის სორტირება, ეს შესანიშნავი ვარიანტია. ეფექტურია; თუმცა, ის დიდ ადგილს იკავებს და არ არის ადვილად გასაცორხიელებელი. შერწყმითი სორტირება ასევე სასარგებლოა დაკავშირებული სიების დასახარისხებლად.
დაეუფლე აქტუალურ პროფესიებს - შემოგვიერთდით სტეპერების დიდ ოჯახში!
IT Academy Step ლიდერი IT სფეროში , ახლა უკვე 100+ ფილიალით!
+995 577 538 549 ქ.თელავი, ნადიკვრის #23
+995 (32) 215-55-51 ქ.თბილისი, ა.ყაზბეგის 34/34 ბ
