نشر توسط:admin Views 35 تاریخ : 2 خرداد 1395 نظرات ()
مرتب سازی با ادغام یک نمونه از الگوریتم های تقسیم و غلبه(Divide-and-Conquer)است.مرتبه ی زمانی این الگوریتم در بدترین حالت نسبت به الگوریتم مرتب سازی درجی رشد کمتری دارد، و علت آن به اساس الگوریتم که تقسیم و غلبه است بر می گردد.
ابتدا داده ها را به دو قسمت تقسیم می کنیم.سپس برای هر مجموعه از داده ها این کار را انجام می دهیم.این کار را آنقدر انجام می دهیم تا هر داده در یک مجموعه ی جداگانه قرار بگیرد.
سپس مجموعه ها دو تا دو تا با هم مقایسه کرده و در صورت نیاز عمل swap را انجام می دهیم.حال برای ادغام مجموعه ها(آرایه های کوچکتر)از اولین ایندکس آرایه ها شروع کرده و داده ها را باهم مقایسه می کنیم.برای مثال مقدار موجود در خانه های هر یک از آرایه ها را با هم مقایسه کرده و مقدار کوچکتر را در آرایه ی جدید قرار می داده و ایندکس آن را یک واحد اضافه می کنیم.این کار را آنقدر انجام می دهیم تا زمانی که یکی از آرایه ها به آخر رسیده باشد.در این صورت داده های موجود در آرایه ی دیگر را به همان ترتیبی که قرار دارند در آرا یه ی جدید قرار دهیم
ادغام(Combine):فرض کنید دو بسته کارت مرتب شده دارید که این بسته ها از بالا به پایین به ترتیب از کوچک به بزرگ قرار داده اید.در این صورت برای ادغام این بسته کارت ها به طوری که بسته ی جدید هم مرتب باشد باید هر بار کارت های دو بسته را با هم مقایسه کرده و هرکدام کوچکتر بود را در بسته ی جدید قرار دهیم.این کار را آنقدر انجام می دهیم تا یکی از بسته ها تمام شود.در این صورت کارت های بسته ی دیگر را بدون تغییر چیدمانشان به بسته ی کارت جدید اضافه می کنیم.
بررسی مرتبه ی زمانی در بهترین حالت:همان طور که از شکل معلوم است می توان داده ها را با درخت نمایش داد.
بهترین حالت زمانی رخ می دهد که وقتی دو آرایه به طول n/2 را با هم ادغام می کنیم تعداد مقایسه ها n/2 باشد.یعنی داده ها مرتب باشند.در این صورت است که بعد از n/2 مقایسه ایندکس یکی از آرایه ها به آخر رسیده و n/2 داده ی دیگر بدون مقایسه در آرایه ی جدید قرار می گیرند.
پس تعداد مقایسه ها در هر سطح درخت به صورت زیر می باشد:
T(n)=n/2+n/4+n/8+…=nlogn(1/2+1/4+1/8+…)=(n/2)logn
Result: (nlogn)
توجه :ارتفاع درخت برابر است با لگاریتم تعداد نودها:logn نود
مرتبه زمانی در بدترین حالت: بدترین حالت زمانی رخ می دهد که وقتی دو آرایه به طولn/2 را با هم ادغام می کنیم تعداد مقایسه ها nباشد.در این صورت تعداد مقایسه ها در هر سطح درخت به صورت زیر می باشد:
T(n)=n+n/2+n/4+…=nlogn(1+1/2+1/4+…)=(n)logn
Result: O(nlogn)
نتیجاً مرتبه ی زمانی در حالت متوسط نیز برابر (ϴ (nlogn می باشد.چرا که میانگین بهترین حالت و بدترین حالتnlogn می شود.
توجه:در مرتب سازی با ادغام علاوه بر آرایه ای برای دخیره ی داده ها به یک آرایه ی دیگر برای ذخیره ی داده های مرتب شده نیاز داریم.(حافظه ی کمکی)
مقایسه ای بین الگوریتم مرتب سازی درجی(Insertion Sort) و ادغامی(Merge Sort) :
مرتب سازی درجی در بدترین حالت مرتبه ی زمانی n^2 را داشته که در مقایسه با مرتب سازی با ادغام با مرتبه زمانی (O(nlognکندتر است. تغییر n به logn کاهش بسیار خوبی است.اگر چه باید اضافه کرد که برای داده های کم، الگوریتم درجی نسبت به ادغامی کاراتر بوده و سرعت بالاتری دارد.اما برای داده های زیاد بر عکس است.چرا که رشد nlogn نسبت به n^2 کمتر است.
محاسبه ی مرتبه زمانی الگوریتم با ادغام از طریق فرمول (T(n)=L T(n/b)+ g(n :
در این فرمول (g(n جمع مرتبه زمانی تقسیم داده ها و ادغام داده هاست.
b تعداد زیرمسئله های بوجود آمده از تقسیم مسئله به مسائل کوچکتر است.و L نیز تعداد زیر مسئله هایی است که بررسی می شوند.
در مرتب سازی با ادغام b=2 و همه ی زیر مسئله های ایجاد شده بررسی می شوند.
(g(n نیز در این ا لگوریتم برابر n است. چرا که تقسیم مسئله به دو قسمت مرتبه زمانی(O(1 دارد و ادغام هر زیر مسئله نیز در بدترین حالت(O(n است.
پس تابع بازگشتی بدست آمده: T(n)=2T(n/2)+n