دنیای فایل

lMerge Sort يكي از روش هاي مرتب سازي داخلي است.

در مرتب سازي به روش ادغام آرايه يا ليست مورد نظر طي چند مرحله به تعدادي آرايه يا ليست تك عضوي شكسته مي شود.

lبعد از شكستن ليست،زيرليست ها را با هم ادغام مي كنيم و

lزير ليست هاي مرتب را طي چند مرحله با هم ادغام مي كنيم تا به يك ليست مرتب با N عضو برسيم.

 

 

تعريف كلاس Element:

Class Element

{

Private:

int key;

Field other;

int link;

public:

Element( ){link=0;};

};

 

ادغام دو ليست مرتب:

Initlist[l],…,initlist[m] initlist[m+1],…,initlist[n]

دو ليست مرتب شده از نوع Elementهستند، به طوري كه:

Initlist [l].key≤…≤ initlist [m].key

Initlist[m+1].key ≤…≤ initlist [n].key

در تابع Mergeاين دو ليست مرتب با يكديگر ادغام مي شوندو

تابع مرتب شده ي جديدي به نام MergedList ايجاد مي شود.

 

Merge Algorithm:

void merge(Element *initList,Element *mergedList,

constintl,constintm,constintn)

 

{

for(int i1=l,iResult=l,i2=m+1;i1<=m&&i2<=n;iResult ++)

if(initlist[i1].getkey()<=initlidt[i2].getkey()){

mergedList[iResult]=initList[i1];

i1++;}

else{

mergedList[iResult]=initList[i2];

i2++;}

if(i1>m)

for(int t=i2;t<=n;t++)

mergedList[iResult+t-i2]=initList[t];

else

for(intt=i1;t<=m;t++)

mergedList[iResult+t-i1]=initList[t];

}

 

تجزيه و تحليل تابع Merge:

مي يابد.كل افزايش iResult،n-l+1است.از اين روحلقه for

حد اكثر n-l+1بار تكرار مي شود.دستور ifحداكثر در هر

تكرار،يك ركورد را جابه جا مي كند.از اين رو كل زمان اجرا

o(n-l+1) است.

مرتب سازي ادغام به صورت تكرار (غير بازگشتي )

 

دراين نسخه ورودي n ليست به طول 1است.اين ليست ها دوبه دوبا هم ادغام مي شوند تا n/2 ليست كه طول هر يك از آن ها 1 است به دست آيد (اگر n فرد باشد آنگاه يك ليست به طول 1 داريم). اين n/2 ليست دوبه دو با هم ادغام مي شوند و اين فرايند تا آنجا ادامه مي يابد كه در انتها به يك ليست برسيم.

در اسلايد بعدي اين فرايند نشان داده شده است.

MergePass Function