در این مقاله الگوریتم مرتب سازی ادغامی یا 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));
}
}
|

لطفا هرگونه پیشنهاد، انتقاد و یا اصلاحیه خود را در رابطه با مطلب فوق، به آدرس ایمیل info@mahampardaz.com ارسال فرمایید.
مرتب سازی ادغامی - ساختمان داده ها - جاوا- merge sort