არსებობს რამდენიმე ძირითადი ალგორითმი მასივის დახარისხების პრობლემის გადასაჭრელად. მათ შორის ერთ-ერთი ყველაზე ცნობილი არის ჩასმის დალაგება. მისი სიცხადისა და სიმარტივის, მაგრამ დაბალი ეფექტურობის გამო, ეს მეთოდი ძირითადად გამოიყენება პროგრამირების სწავლებაში. ის საშუალებას გაძლევთ გაიგოთ დახარისხების ძირითადი მექანიზმები.
ალგორითმის აღწერა
ჩასმის დახარისხების ალგორითმის არსი არის ის, რომ საწყის მასივის შიგნით ყალიბდება სწორად მოწესრიგებული სეგმენტი. თითოეული ელემენტი სათითაოდ შედარებულია შემოწმებულ ნაწილთან და ჩასმულია სწორ ადგილას. ამრიგად, ყველა ელემენტის გამეორების შემდეგ, ისინი რიგდებიან სწორი თანმიმდევრობით.
ელემენტების შერჩევის თანმიმდევრობა შეიძლება იყოს ნებისმიერი, მათი შერჩევა შესაძლებელია თვითნებურად ან რაიმე ალგორითმის მიხედვით. ყველაზე ხშირად, თანმიმდევრული ჩამოთვლა გამოიყენება მასივის დასაწყისიდან, სადაც იქმნება მოწესრიგებული სეგმენტი.
დახარისხების დასაწყისი შეიძლება ასე გამოიყურებოდეს:
- აიღეთ მასივის პირველი ელემენტი.
- რადგან შედარება არაფერია, აიღეთ თავად ელემენტი შეკვეთის მიხედვითთანმიმდევრობა.
- გადადით მეორე პუნქტზე.
- შეადარეთ პირველთან დალაგების წესის მიხედვით.
- საჭიროების შემთხვევაში შეცვალეთ ელემენტები ადგილებზე.
- მიიღეთ პირველი ორი ელემენტი მოწესრიგებული თანმიმდევრობით.
- გადადით მესამე პუნქტზე.
- შეადარეთ მეორეს, შეცვალეთ საჭიროების შემთხვევაში.
- თუ ჩანაცვლება გაკეთდა, შეადარეთ ის პირველს.
- მიიღეთ სამი ელემენტი მოწესრიგებული თანმიმდევრობით.
და ასე გაგრძელდება ორიგინალური მასივის ბოლომდე.
რეალური ცხოვრების ჩასმის დალაგება
სიცხადისთვის, ღირს მაგალითის მოყვანა, თუ როგორ გამოიყენება ეს დახარისხების მექანიზმი ყოველდღიურ ცხოვრებაში.
აიღეთ, მაგალითად, საფულე. ასი, ხუთასი და ათასდოლარიანი კუპიურები უწესრიგოდ დევს ბანკნოტების განყოფილებაში. ეს არეულობაა, ასეთ აურზაურში ძნელია დაუყოვნებლივ იპოვოთ სწორი ფურცელი. ბანკნოტების მასივი უნდა იყოს დახარისხებული.
პირველი არის 1000 რუბლის ბანკნოტი, შემდეგ კი - 100. ვიღებთ ასს და ვათავსებთ წინ. ზედიზედ მესამე არის 500 მანეთი, მისი კანონიერი ადგილი ასიდან ათასამდეა.
ასევე ვახარისხებთ მიღებულ ბარათებს "სულელის" თამაშისას, რათა გაადვილდეს მათზე ნავიგაცია.
ოპერატორები და დამხმარე ფუნქციები
ჩასმის დალაგების მეთოდი შესაყვანად იღებს დასალაგებლად საწყის მასივს, შედარების ფუნქციას და, საჭიროების შემთხვევაში, ფუნქციას, რომელიც განსაზღვრავს ელემენტების ჩამოთვლის წესს. ამის ნაცვლად ყველაზე ხშირად გამოიყენებარეგულარული მარყუჟის განცხადება.
პირველი ელემენტი თავისთავად არის მოწესრიგებული ნაკრები, ამიტომ შედარება იწყება მეორედან.
ალგორითმი ხშირად იყენებს დამხმარე ფუნქციას ორი მნიშვნელობის გაცვლისთვის (სვოპ). ის იყენებს დამატებით დროებით ცვლადს, რომელიც მოიხმარს მეხსიერებას და ოდნავ ანელებს კოდს.
ალტერნატივა არის ელემენტების ჯგუფის მასიურად გადატანა და შემდეგ არსებულის თავისუფალ სივრცეში ჩასმა. ამ შემთხვევაში, შემდეგ ელემენტზე გადასვლა ხდება მაშინ, როდესაც შედარებამ დადებითი შედეგი გამოიღო, რაც მიუთითებს სწორ მიმდევრობაზე.
განხორციელების მაგალითები
კონკრეტული განხორციელება დიდწილად დამოკიდებულია გამოყენებული პროგრამირების ენაზე, მის სინტაქსსა და სტრუქტურებზე.
კლასიკური C დანერგვა დროებითი ცვლადის გამოყენებით მნიშვნელობების გაცვლისთვის:
int i, j, temp; for (i=1; i =0; j--) { if (მასივი[j] < ტემპი) შესვენება; მასივი[j + 1]=მასივი[j]; მასივი[j]=ტემპერატურა; } }
PHP დანერგვა:
ფუნქცია insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
აქ, ჯერ ყველა ელემენტი, რომელიც არ ემთხვევა დალაგების მდგომარეობას, გადაინაცვლებს მარჯვნივ, შემდეგ კი მიმდინარე ელემენტი ჩასმულია თავისუფალ სივრცეში.
Java კოდის გამოყენებით while loop:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
კოდის ზოგადი მნიშვნელობა უცვლელი რჩება: მასივის თითოეული ელემენტი თანმიმდევრულად შედარებულია წინა ელემენტებთან და საჭიროების შემთხვევაში იცვლება მათთან.
სავარაუდო გაშვების დრო
ცხადია, საუკეთესო შემთხვევაში, ალგორითმის შეყვანა იქნება უკვე სწორად შეკვეთილი მასივი. ამ სიტუაციაში, ალგორითმს უბრალოდ მოუწევს თითოეული ელემენტის შემოწმება, რათა დარწმუნდეს, რომ ის სწორ ადგილას არის გაცვლის გარეშე. ამრიგად, გაშვების დრო პირდაპირ იქნება დამოკიდებული ორიგინალური მასივის სიგრძეზე O(n).
ყველაზე ცუდი შემთხვევის შეყვანა არის საპირისპირო თანმიმდევრობით დალაგებული მასივი. ამას დასჭირდება პერმუტაციების დიდი რაოდენობა, გაშვების ფუნქცია დამოკიდებული იქნება ელემენტების რაოდენობაზე კვადრატში.
სრულად შეურიგებელი მასივის პერმუტაციების ზუსტი რაოდენობა შეიძლება გამოითვალოს ფორმულით:
n(n-1)/2
სადაც n არის ორიგინალური მასივის სიგრძე. ამრიგად, 100 ელემენტის სწორი თანმიმდევრობით მოწყობას დასჭირდება 4950 პერმუტაცია.
ჩასმის მეთოდი ძალიან ეფექტურია მცირე ან ნაწილობრივ დახარისხებული მასივების დასალაგებლად. თუმცა, გამოთვლების მაღალი სირთულის გამო მისი ყველგან გამოყენება არ არის რეკომენდებული.
ალგორითმი გამოიყენება როგორც დამხმარე სხვა დახარისხების სხვა უფრო რთულ მეთოდებში.
ტოლი მნიშვნელობების დალაგება
ჩასმის ალგორითმი მიეკუთვნება ეგრეთ წოდებულ სტაბილურ ჯიშებს. Ეს ნიშნავს,რომ ის არ ცვლის იდენტურ ელემენტებს, მაგრამ ინარჩუნებს მათ თავდაპირველ წესრიგს. სტაბილურობის ინდექსი ხშირ შემთხვევაში მნიშვნელოვანია სწორი შეკვეთისთვის.
ზემოაღნიშნული ცეკვაში ჩასმის დალაგების შესანიშნავი ვიზუალური მაგალითია.
