دسته بندی | کامپیوتر |
بازدید ها | 4 |
فرمت فایل | ppt |
حجم فایل | 362 کیلو بایت |
تعداد صفحات فایل | 55 |
پاورپوینت MergeSort ارائه دو الگوریتم برای ادغام دو لیست مرتب
ارائه دوالگوریتم برای ادغام دو لیست مرتب
الگوریتم غیر بازگشتی Merge Sort
الگوریتم بازگشتی Merge Sort
Merge Sort:
Merge Sort یکی از روش های مرتب سازی داخلی است.
در مرتب سازی به روش ادغام آرایه یا لیست مورد نظر طی چند مرحله به تعدادی آرایه یا لیست تک عضوی شکسته می شود.
نکات:تعداد آرایه ها یا لیست های تک عضوی همان تعداد اولیه ی نودها یا اعضای آرایه هستند .
طول لیست یا آرایه ی اولیه را Nدر نظر بگیرید.
به جای آرایه لیست به کار می بریم .
بعد از شکستن لیست،زیرلیست ها را با هم ادغام می کنیم و
زیرلیست های مرتب دیگری بدست می آوریم .
زیر لیست های مرتب را طی چند مرحله با هم ادغام می کنیم تا به یک لیست مرتب با 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 ایجاد می شود.
ppt: نوع فایل
سایز:362 KB
تعداد اسلاید:55