تیم برنامه نویسی گروه تمدن

به نام خدا

یکی از بهترین انواع مرتب سازی روش merg sort می باشد. برای درک بهتر، این قسمت را با یک مثال آموزش می دهیم:

می خواهیم لیست روبه­ رو را به روش merge sort  مرتب کنیم : 8,2,4,6,9,7,10,1,5,3

merge sort با قسمت کردن و جدا کردن لیست به دو قسمت، با اعضا منحصر بفرد به صورت متوالی شروع می­ شود:

حال این لیست ها را به صورت دوتایی مرتب می کنیم  تا به لیست اصلی برسیم، شکل زیر نشان دهنده این موضوع است:

برای انجام merge sort  ما یک لیست را به 2 تا زیرلیست که اندازه آنها ( طول آنها ) تقریباً یکسان هستند تقسیم می­کنیم. هر کدام از زیر لیستها را با استفاده از اگوریتم merge sort مرتب می­کنیم، سپس دو زیر لیست را به هم می چسبانیم. برای این کار ابتدا تابعی به نام merge تعریف می کنیم که در آن یک آرایه را با گرفتن اندیس ابتدا و انتها به دو قسمت با طول مساوی تقسیم می کند:

void merge(int arr[ ] , int low, int high){
int mid=(low+high)/2;
   int j = low;
   for (int i = mid + 1 ; i <= high ; i++){
       while (arr[ j ] <= arr[ i ] && j < i)
           j++;
       if (j == i)
           break;
       int t = arr[ i];
       for (int k = i ; k > j ; k--)
           arr[ k ] = arr[k-1];
       arr[ j ] = t;
   }//end for i
}//end merge 

سپس تابعی دیگر تعریف می کنیم تا با استفاده از تابع قبلی آرایه منظم شده را به ما ارائه دهد.

void merge_sort (int arr[ ] , int low , int high)
{
    if (low >= high)
     return;
    int mid = (low + high) / 2;
    merge_sort (arr , low , mid);
    merge_sort (arr , mid + 1 , high);
    merge(arr , low  , high);
}//end merge_sort

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

در این الگوریتم پیچیدگی در بهترین و بدترین حالت برابر است با n*logn

برای دانلود این الگوریتم در یک برنامه می توانید روی لیک زیر کلیک نمایید:

دانلود سورس کد و فایل اجرایی برنامه مرتب سازی به روش Merge Sort به صورت رایگان با لینک مستقیم