الخوارزميات الحلقة العشرون merge sort

                               بسم الله الرحمن الرحيم 

ما هو merge sort ؟

 

من أفضل خوارزميات الترتيب لأنها تأخد وقت أقل من الخوارزميات الأخري تعتمد علي المقارنة لترتيب العناصر .

مثال للتوضيح :

قم بترتيب العناصر الأتية تصاعدياً.

خطوات الترتيب :

1- تقسيم المصفوفة إلى مصفوفتين

2- تقسيم كل مصفوفة إلى مصفوفتين حتى الوصول إلى مصفوفات بها عنصر واحد فقط

3- دمج كل مصفوفة مع المجاورة لها بالترتيب بناءاً على المقارنة

4- إنشاء مصفوفة جديدة من كل مصفوفتين سابقتين بناءاً على مقارنة أول عنصر فى مصفوفة بأول عنصر فى المصفوفة الأخرى وهكذا حتى الحصول على مصفوفة مرتبه من مصفوفتين مرتبتين

5- إنشاء مصفوفة جديدة من كل مصفوفتين سابقتين حسب الترتيبب يتم ذلك بمقارنة العنصر الأول من كلا المصفوفتين وأخذ الأصغر ثم المقارنة من جديد وأخذ الأصغر وهكذا حتى الوصول إلى مرحلة تكون فيها مصفوفة واحدة مرتبة

تعقيدات الوقت 

o(log n)

كود جافا للخوارزمية

class MergeSort
{
 
    void merge(int arr[], int l, int m, int r)
    {
               int n1 = m - l + 1;
        int n2 = r - m;

            int L[] = new int [n1];
        int R[] = new int [n2];

               for (int i=0; i<n1; ++i)
            L[i] = arr[l + i];
        for (int j=0; j<n2; ++j)
            R[j] = arr[m + 1+ j];


    
        int i = 0, j = 0;

              int k = l;
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
            {
                arr[k] = L[i];
                i++;
            }
            else
            {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

              while (i < n1)
        {
            arr[k] = L[i];
            i++;
            k++;
        }

               while (j < n2)
        {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

   
    void sort(int arr[], int l, int r)
    {
        if (l < r)
        {
                       int m = (l+r)/2;

                  sort(arr, l, m);
            sort(arr , m+1, r);

           
            merge(arr, l, m, r);
        }
    }

      static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

        public static void main(String args[])
    {
        int arr[] = {12, 11, 13, 5, 6, 7};

        System.out.println("Given Array");
        printArray(arr);

        MergeSort ob = new MergeSort();
        ob.sort(arr, 0, arr.length-1);

        System.out.println("\nSorted array");
        printArray(arr);
    }
}

لمتابعة الحلقة السابقة 

الخوارزميات الحلقة التاسعة عشر shell sort