; როგორ განვახორციელოთ Merge Sort-ი პროგრამირების ენაში Python? - IT Academy STEP Tbilisi როგორ განვახორციელოთ Merge Sort-ი პროგრამირების ენაში Python? - IT Academy STEP Tbilisi

თბილისი, ჯანო ბაგრატიონის 6

როგორ განვახორციელოთ Merge Sort-ი პროგრამირების ენაში Python?

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

სორტირების საფუძვლები

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

გარე სორტირება – როცა მთლიანი დასახარისხებელი მონაცემი ერთდროულად ვერ მოთავსდება მეხსიერებაში. ამას გარე სორტირებას უწოდებენ. მაგალითად, Merge Sort

შიდა სორტირება – როცა მთლიანი მონაცემი მოთავსებულია მეხსიერებაში, მაშინ ასეთ სორტირებას შიდა სორტირებას ეძახიან.

რა არის Merge Sort-ი?

Merge Sort-ი არის რეკურსიული (განმეორებითი) & „divide-and-conquer (დაყავი და იბატონე)“ ტიპის ალგორითმი. Divide and conquer ალგორითმი მუშაობს პრობლემების ორ ან მეტ, იგივე ან დაკავშირებული ტიპის  პატარა პრობლემებად რეკურსიული დაშლის მეთოდით, სანამ ისინი ისე არ გამარტივდება, რომ მათი გადაჭრა პირდაპირ მოხდეს. ზემოთ ხსენებული იდეის საფუძველზე მუშაობს Merge Sort-ი.

Merge Sort-ში, ხდება პუნქტის ან ვთქვათ სიის ან მასივის რამდენიმე პატარ-პატარა ჩანაწერებად დაშლა, სანამ თითოეული პატარა ჩანაწერი არ იქნება მხოლოდ ერთი ელემენტისგან შემდგარი და პატარ-პატარა ჩანაწერები ერთმანეთს ისე არ შეერწყმება, თუ შედეგად მოცემულ სორტირებული ჩანაწერებს არ მივიღებთ. თუ სია ერთზე მეტი ჩანაწერისგან შედგება, ჩვენ ვყოფთ სიას ორ ნაწილად და რეკურსიულად ვიძახებთ merge sort-ს ორივე ნაწილზე.

ორი ნაწილის შერწყმისთვის შედარების დროს, ორივე სიის პირველ ელემენტს უნდა მივაქციოთ ყურადღება. თუ ორი ნაწილი ერთხელ დახარისხდა, მაშინ ფუნდამენტური ოპერაცია სახელწოდებით the merge შესრულდება. Merging-ი (შერწყმა) არის პროცესი, სადაც ორი შედარებით პატარა სორტირებული სია ერთიანდება ერთ, სორტირებულ ახალ სიად.

მნიშვნელოვანი საკითხები, რაც უნდა გვახსოვდეს:

  • დროის სირთულე: MergeSort-ის დროის სირთულე არის BigO(nLogn) სამივე შემთხვევაში (ყველაზე ცუდი, საშუალო და ყველაზე კარგი), რადგან Merge Sort-ი ყოველთვის ყოფს მასივს ან სიას ორ ნაწილად და მოითხოვს შესაბამის დროს ორი ნაწილის შერწყმისთვის.
  • დამხმარე სივრცე: O(n)
  • ალგორითმული პარადიგმა: დაყავი და იბატონე
  • სტაბილური: დიახ

Merge Sort-ის წარმოდგენა დიაგრამაზე

დააკვირდით Merge Sort-ის განხორციელების ჩვენებას დიაგრამაზე, იმისთვის რომ მისი კონცეფცია უფრო გასაგები გახდეს თქვენთვის.

დახარისხებული თანმიმდევრობა

დასაწყისში შეიძლება გვქონდეს დაუხარისხებელი თანმიმდევრობა. ვთქვათ ჩვენი მიზანია მოცემული პუნქტების ზრდადობის მიხედვით დაწყობა, ამისთვის გამოიყენება Merge Sort-ის ზემოთ მოცემული მიდგომა.

Merge Sort-ის ალგორითმი

პროგრამა Python3-ზე

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

def merge_sort(arr):

 # checking if array lenght is greter than 1 and this is the base case

    if len(arr)>1:

 # divide the given array in two half

        mid = len(arr)/2

 # creating two halves for the array

        lefthalf = arr[:mid] # slice operation

        righthalf = arr[mid:]

 

 # call the merge_sort rescursively on the both halves

        merge_sort(lefthalf)

        merge_sort(righthalf)

 

 # Making some index variable and initilize them to 0

        i=0

        j=0

        k=0 # this will relate to the final array

 

 # while loop for checking the mid point

        while i < len(lefthalf) and j < len(righthalf):

 # check if the lefthalf is less than the right

            if lefthalf[i] < righthalf[j]:

 # assign the kth element to lefthalf and increment the i index

                arr[k]=lefthalf[i]

                i=i+1

 

            else:

 # assign to the righthaflf and increment the j index

                arr[k]=righthalf[j]

                j=j+1

 # then increment the k element

            k=k+1

 

 # check the lefthalf and continue the similary process

        while i < len(lefthalf):

            arr[k]=lefthalf[i]

            i=i+1

            k=k+1

 

 # check the righthalf

        while j < len(righthalf):

            arr[k]=righthalf[j]

            j=j+1

            k=k+1

# putting some value in the array

arr = [11,2,5,4,7,6,8,1,23]

# call the merge_sort function

merge_sort(arr)

arr

 

ზემოთ მოყვანილ მაგალითში mergesort-ის გამოძახება რეკურსიულად ხდება, სანამ სორტირება არ დააკმაყოფილებს საბაზო პირობას. “I and “J” ინდექსი ძირითადად ამოწმებს თუ რომელ ნაწილში ვართ ჩვენ ანუ ეს მარცხენა ნაწილია თუ მარჯვენა. სინამდვილეში სამი while loop- ასრულებს დახარისხებული პატარა სიების შერწყმას. საწყის ეტაპზე თუ სიის ან მასივის სიგრძე არის 1 ან 0, მაშინ სორტირება აღარ არის საჭირო, რადგან ეს არის საწყისი პირობა.

გამოწვევა: სცადეთ დინამიურად განახორციელოთ ეს, მნიშვნელობების მასივში კოდირების ნაცვლად.

IT Academy STEP – თქვენი წარმატება იწყება აქ !

იზრუნეთ მომავალზე, შეისწავლეთ პროგრამირება, მიიღეთ ხარისხიანი ცოდნა  და უზარმაზარი გამოცდილება!

დეტალური ინფორმაციისათვის და კურსზე ჩასაწერად, გთხოვთ გაიაროთ რეგისტრაცია პროგრამული უზრუნველყოფის დეველოპერი

 

გახსოვდეთ, წარმატებული IT სპეციალისტი უპრობლემოდ პოულობს მაღალანაზღაურებად სამსახურს და ერთვება მსოფლიოს ნებისმიერი წერტილიდან

მიიღეთ საჭირო ცოდნა

შემოგვიერთდით მსოფლიო ბრენდ  IT აკადემია STEP-ში!

თბილისი,
ჯანო ბაგრატიონი #6
+995 (32) 215-55-51
+995 (32) 215-50-05

დარეკეთ ან დარეგისტრირდით ეხლავე, ჩვენი კვალიფიციური სპეციალისტები დაგიკავშირდებიან უმოკლეს დროში

რეგისტრაცია

სახელი, გვარი*
ტელეფონი*
E-mail*
სად გაეცანით ინფორმაციას ღია კარის დღის შესახებ?*


ახალი ამბები