دانلود   پاورپوینت Merge Sort

توضیحات محصول

دانلود پاورپوینت Merge Sort با فرمت ppt ودر 54 اسلاید قابل ویرایش

قسمتی از متن پاورپوینت Merge Sort

Overview:

ارائه دوالگوريتم براي ادغام دو ليست مرتب

الگوريتم غير بازگشتي Merge Sort

الگوريتم بازگشتي Merge Sort

Merge Sort:

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

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

نكات:تعداد آرايه ها يا ليست هاي تك عضوي همان تعداد اوليه ي نودها يا اعضاي آرايه هستند .

طول ليست يا آرايه ي اوليه را Nدر نظر بگيريد.

به جاي آرايه ليست به كار مي بريم .

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

if(initlist[i1].getkey()

mergedList[iResult]=initList[i1];

i1++;}

else{

mergedList[iResult]=initList[i2];

i2++;}

if(i1>m)

for(int t=i2;t

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

else

for(intt=i1;t

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

}

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

 در هر تكرار از حلقه ي for،هرiResultيك واحد افزايش

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

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

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

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

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

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

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

از آنجا كه مرتب سازي ادغام شامل چند مرحله است از اين رو بهتر است ابتدا تابعي براي اين منظور معرفي كنيم:

MergePass Function

پس از آن به معرفي MergeSort Algorithm مي پردازيم كه مرتب سازي را با احضار مكررتابع Merge Passانجام مي دهد.