در این مقاله الگوریتم مرتب سازی ادغامی یا Merge Sort مورد بررسی قرار می گیرد



الگوریتم مرتب سازی ادغامی ( Merge Sort )

قبل از شروع هرگونه توضیحی به دقت به تصویر زیر توجه نمایید و خودتان سعی کنید تا با توجه به این مثال به درکی هرچند مختصر نسبت به این الگوریتم، دست یابید.

مرتب سازی ادغامی  merge sort

برای مشاهده تصویر در ابعاد بزرگتر، روی آن کلیک کنید

 

همانطور که در شکل فوق مشاهده می شود، الگوریتم merge sort از دو بخش Divide و Merge تشکیل می شود. زمانی که یک آرایه از اعداد جهت sort کردن به روش در اختیار ما قرار داده می شود، ابتدا آرایه را به دو آرایه با طول n/2 تقسیم می کنیم. دقت کنید که این عمل تقسیم سازی آرایه را در دو زیر آرایه حاصل و تمام زیر آرایه های دیگر حاصل از مراحل تقسیم سازی قبلی نیز اعمال می کینم تا جایکه زیر آرایه های حاصل تک عضوی گردند. سپس نوبت به انجام عملیات merge کردن می رسد. در این مرحله هر دو زیر آرایه تک عضوی را sort کرده و سپس merge می نماییم. نتیجه این عمل تشکیل یک زیر آرایه مرتب شده خواهد بود. عملیات merge کردن را تا جایی ادامه می دهیم تا  آرایه اولیه «به صورت مرتب شده» حاصل شود.

«نکته» این الگوریتم مشابه الگوریتم مرتب سازی سریع یا quick sort، از روش تقسیم و حل یا divide-and-conquer strategy و با استفاده از تکنیک بازگشتی « Recursive » حل می گردد. البته این الگوریتم از طریق روش تکراری نیز قابل پیاده سازی می باشد.

 

بررسی پیچیدگی زمانی الگوریتم

W.C :  o(n log n)

AVG.C: o(n log n)

B.C: o(n log n)

همانگونه که مشاهده می شود، سرعت الگوریتم در بدترین حالت آن هم خوب است. ولی از لحاظ مصرف حافظه اشکال عمده آن این است که به یک بافر به اندازه آرایه اولیه نیاز دارد. این عیب یا نارسایی در مورد آرایه های بزرگ بویژه اگر عناصر آرایه از نوع Structure باشد، بسیار محسوس تر می شود.

 

public class Merge {
    public static void sort(Comparable[] a) {
        sort(a, 0, a.length);
    }
    // Sort a[lo, hi).
    public static void sort(Comparable[] a, int lo, int hi) {
        int N = hi - lo;        // number of elements to sort

        // 0- or 1-element file, so we're done
        if (N <= 1) return;

        // recursively sort left and right halves
        int mid = lo + N/2;
        sort(a, lo, mid);
        sort(a, mid, hi);

        // merge two sorted subarrays
        Comparable[] aux = new Comparable[N];
        int i = lo, j = mid;
        for (int k = 0; k < N; k++) {
            if      (i == mid)  aux[k] = a[j++];
            else if (j == hi)   aux[k] = a[i++];
            else if (a[j].compareTo(a[i]) < 0) aux[k] = a[j++];
            else                               aux[k] = a[i++];
        }

        // copy back
        for (int k = 0; k < N; k++) {
            a[lo + k] = aux[k];
        }
    }

   /***********************************************************************
    *  Check if array is sorted - useful for debugging
    ***********************************************************************/
    private static boolean isSorted(Comparable[] a) {
        for (int i = 1; i < a.length; i++)
            if (a[i].compareTo(a[i-1]) < 0) return false;
        return true;
    }

// test client
    public static void main(String[] args) {
        int N = 10;

        // generate N random real numbers between 0 and 1
        long start = System.currentTimeMillis();
        Double[] a = new Double[N];
        for (int i = 0; i < N; i++)
            a[i] = Math.random();

        System.out.print("primaray array is: \n");
        for(int k=0; k<N; k++){
            System.out.print(a[k]);
            if (k<9)
               System.out.print(" , ");
        }
        System.out.print("\n");

        long stop = System.currentTimeMillis();
        double elapsed = (stop - start) / 1000.0;
        System.out.println("Generating input:  " + elapsed + " seconds");

        // sort them
        start = System.currentTimeMillis();
        sort(a);
        stop = System.currentTimeMillis();
        elapsed = (stop - start) / 1000.0;
        System.out.print("\nsorted array is: \n ");
        for(int k=0; k<N; k++){
            System.out.print(a[k]);
            if (k<9)
               System.out.print(" , ");
        }
        System.out.print("\n");
        System.out.print("Start sort time (in mili second) is: " + start +"\n");
        System.out.print("end sort time (in mili second) is: " + stop +"\n");

        System.out.println("Mergesort: " + elapsed + " seconds");
        System.out.println(isSorted(a));

       
    }
}

 

 

دانلود برنامه هاي مورد استفاده در اين مقاله

 


مرتب سازی ادغامی - ساختمان داده ها - جاوا- merge sort



نظرات کاربران

نام و نام خانوادگی :
ایمیل :
متن نظر :