تفکیک و پردازش داده‌ها

روش کار الگوریتم مرتب‌سازی ادغامی

ابتدا فهرستی از داده‌ها که قرار است مرتب شوند به 2 فهرست به طول مساوی تقسیم می‌شوند و سپس فهرست‌های تولید شده به روش بازگشتی با صدا زدن تابع MergSort هر کدام به دو زیرفهرست تقسیم می‌شوند. این عمل آنقدر ادامه پیدا می‌کند تا به فهرست‌هایی برسیم که طول هر کدام ? باشد.

تمام زیرفهرست‌های تولیدشده مرتب می‌شوند و سپس از پایین به بالا با فهرست‌های مجاور خود ادغام شده و فهرست جدیدی تولید می‌شود. این فهرست‌ها نیز با فهرست‌های مجاور خود ادغام می‌شوند. آن قدر این فهرست‌ها با هم ترکیب می‌شوند تا به فهرست نهایی برسیم. در هر ادغام مرتب بودن داده‌ها حفظ می‌شود. حال این روش را با یک مثال توضیح می‌دهیم.

فرض کنید داده‌های ما مجموعه‌ای به نام A‌ است که به‌صورت زیر تعریف شده است:

A = { 5,2,4,7,1,3,2,6}

ابتدا مجموعه A را به 2 زیرمجموعه با طول یکسان به نام‌های A1و A2 تقسیم می‌کنیم:

A1={5,2,4,7}, A2={ 1,3,2,6}

سپس هر کدام از این مجموعه‌ها را به 2 مجموعه با طول مساوی تقسیم کرده و در نهایت به ? مجموعه به‌صورت زیر می‌رسیم:

B={5,2}, C={4,7}, D={1,3}, E={2,6}

از مجموعه‌های بالا فقط مجموعه B نیاز به مرتب‌سازی دارد. پس از مرتب کردن جدول B باید مجموعه‌ها را با هم ادغام کنیم.

عمل ادغام به این صورت است که ابتدا اولین عنصر از هر دو مجموعه‌ را با هم مقایسه کرده و عنصر کوچک‌تر را در مجموعه سومی قرار می‌دهیم که همان خروجی این مرحله است. سپس عنصر بعدی را از همان مجموعه‌ای انتخاب می‌کنیم که عنصر اول که در مجموعه سوم قرار گرفته است. سپس این عمل را آنقدر ادامه می‌دهیم که تمامی عناصر یکی از 2 مجموعه در مجموعه سومی که نتیجه حاصل از ادغام دو مجموعه در آن ذخیره شده ‌است، قرار بگیرد. سپس باقی عناصر مجموعه دوم به ترتیب به مجموعه سوم منتقل می‌شود.

شبه‌کد این الگوریتم به‌صورت زیر است:

function merge_sort(m) {

var list left, right, result

if length(m) «= 1

return m

var middle = length(m) / 2

for each x in m up to middle

add x to left

for each x in m after middle

add x to right

left = merge_sort(left)

right = merge_sort(right)

result = merge(left, right)

return result

}

function merge(left, right) {

var list result

while length(left) » 0 and length(right) » 0

if first(left)«=first(right)

append first(left) to result

left = rest(left)

else

append first(right) to result

right = rest(right)

end while

while length(left) » 0

append left to result

while length(right) » 0

append right to result

return result}

اگر زمان لازم برای مرتب‌سازی آرایه N‌عضوی به روش ادغام برابر (T(N باشد داریم:

T(N) = 2T(N/2) + N

در این الگوریتم در هر مرحله آرایه به 2 آرایه شکسته می‌شود و در هر مرحله از ادغام نیز باید N مقایسه صورت بگیرد.

در نتیجه در بدترین حالت تعداد مقایسه‌های این الگوریتم برابر (n[log n] -2[log n] +1) است و چون عمل غالب در این الگوریتم مانند باقی الگوریتم‌های مرتب‌سازی عمل مقایسه است.

پس مرتبه اجرایی این الگوریتم برابر (o(nlogn است. این الگوریتم در بدترین حالت ?? بار سریع‌تر از الگوریتم مرتب‌سازی حبابی (Bubble sort) است. در جاهایی بدترین حالت این الگوریتم از لحاظ زمانی برابر بهترین حالت الگوریتم سریع (Quick sort) با داده‌های یکسان است.