الگوریتم ادغام

الگوریتم‌های ادغام الگوریتم‌هایی هستند که چند آرایهٔ مرتب را به عنوان ورودی دریافت می‌کنند و آرایه‌ای مرتب متشکل از اعضای کلیهٔ آرایه‌های ورودی را خروجی می‌دهند. از این الگوریتم به عنوان زیرروال در الگوریتم‌های مرتب‌سازی استفاده می‌شود.

ادغام دو لیست

ادغام دو لیست در زمان اجرای خطی و با حافظهٔ اضافی خطی قابل انجام است. کد زیر در زبان پایتون این عملیات را نشان می‌دهد. در این کد با گرفتن آرایه‌ای خالی به عنوان آرایهٔ جواب عملیات را آغاز می‌کنیم. با شروع از ابتدای دو آرایهٔ ورودی و با مقایسه اعضای آن‌ها به ترتیب، عضو کوچکتر را به آرایهٔ جواب می‌افزاییم. در آخر اعضایی از یک آرایهٔ ورودی باقی می‌ماند؛ آن‌ها را نیز به همان ترتیب به آرایهٔ جواب می‌افزاییم.

def merge(a,b):
    c = []
    i = j = 0
    while i <len(a) and j <len(b):
        if a[i] <b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1
    while i <len(a):
        c.append(a[i])
        i += 1
    while j <len(b):
        c.append(b[j])
        j += 1
    return c

ادغام $k$ لیست

می‌خواهیم الگوریتمی ارائه دهیم که به عنوان ورودی $k$ آرایهٔ مرتب را بگیرد و آرایه‌ای مرتب از کلیهٔ اعضای آن‌ها را خروجی دهد. ادغام $k$ آرایه مرتب، در الگوریتم‌های مرتب‌سازی بسیاری از جمله مرتب‌سازی شکیبانه و مرتب‌سازی خارجی استفاده می‌شود.

برای ادغام $k$ آرایه یا لیست مرتب چندین الگوریتم وجود دارد که در اینجا به ۳ مورد از آن‌ها اشاره می‌کنیم.

الگوریتم اول

یک الگوریتم ساده اما طولانی این است که همانند روشی که برای دو لیست عمل کردیم، با شروع از ابتدای همه لیست‌ها، کمینه را پیدا کرده و آن را به آرایهٔ جواب اضافه نموده و این عمل تا زمانی که کل لیست‌ها خالی شوند، تکرار می‌کنیم. زمان اجرای این الگوریتم، $O(nk)$ است.

الگوریتم دوم

در این الگوریتم، ابتدا لیست اول را با لیست دوم ادغام می‌کنیم، سپس حاصل را با لیست سوم ادغام می‌کنیم و همین گونه ادامه می‌دهیم تا به یک لیست نهایی برسیم. چون زمان اجرای ادغام دو لیست با $n$ عضو در کل، $O(n)$ است، بنابراین زمان اجرای این الگوریتم برابر است با:

$(k-1){\frac {n}{k}}+(k-1){\frac {n}{k}}+(k-2){\frac {n}{k}}...+{\frac {n}{k}}={\frac {k(k-1)}{2}}\times {\frac {n}{k}}+(k-1){\frac {n}{k}}=O(nk)$

در محاسبه زمان فرض شده‌است تعداد اعضای همهٔ لیست‌ها برابر و تعداد کل اعضا $n$است. در این صورت اعضای لیست اول و دوم در کلیه ادغام‌ها یعنی $k-1$ ادغام، اعضای لیست سوم از ادغام دوم به بعد یعنی در $k-2$ ادغام و به همین ترتیب تا لیست آخر در ادغام آخر حضور دارند. اعضای هر لیست را به تعداد تکرار آن‌ها در ادغام‌ها باید بشماریم که در عبارت بالا انجام شده‌است.

الگوریتم سوم

برای سریع‌تر انجام دادن این عملیات، از هرم کمینه استفاده می‌کنیم. ابتدا با استفاده از عضو اول همهٔ لیست‌ها، یک هرم کمینه می‌سازیم. این عمل می‌تواند در زمان اجرای $O(n)$ انجام شود. سپس هربار کمینه که عضو اول هرم است را خروجی داده و عضو بعدی آرایه شامل آن را جایگزینش می‌کنیم (اگر عضو بعدی نداشت، بی‌نهایت را جایگزین آن می‌کنیم). سپس باید دوباره هرم را به هرم کمینه تبدیل کنیم که این کار زمان اجرای $O(log(k))$ را داراست. اگر در کل $n$عدد در کل لیست‌ها داشته باشیم، کل عملیات دارای زمان اجرای $O(nlog(k))$ خواهد بود.

ادغام موازی

الگوریتم زیر در زبان پایتون چگونگی این ادغام را نشان می‌دهد. ورودی‌های این تابع، دو آرایهٔ مرتب $A$ به طول $n$ و $B$ به طول $m$ است و خروجی آرایهٔ $C$ به طول $m+n$ است. به این ادغام، موازی گویند چرا که دو خط نهایی تابع زیر، ورودی‌هایی کاملاً جدا از هم دارند پس می‌توانند به‌طور موازی انجام شوند. از این ادغام در مرتب‌سازی ادغامی موازی استفاده می‌شود. (در این الگوریتم از جستجوی دودویی استفاده‌شده‌است)

def parallel_merge(A, B, C):
    if len(A) <len(B):
        A, B = B, A #make sure that A is the bigger Array
    if len(A) == 0:
        return  #there is nothing to merge
    r = len(A) // 2
    s = Binary-search(A[r], B)
    t = r + s
    C[t] = A[r]
    # do in parallel
    merge(A[0:r], B[0:s], C[0:t])
    merge(A[r+1:len(A)], B[s+1:len(B)], C[t+1:len(C)])

کاربردهای ادغام

مرتب‌سازی ادغامی

مهم‌ترین کاربرد این الگوریتم در مرتب‌سازی ادغامی است. این مرتب‌سازی، یک مرتب‌سازی مقایسه‌ای است که از الگوریتم تقسیم و حل استفاده می‌کند. به این گونه که به‌طور بازگشتی، آرایه را به دو آرایه با طول مساوی تقسیم می‌کند تا به آرایه‌هایی با طول یک برسد. سپس به‌طور بازگشتی آرایه‌ها را باهم ادغام می‌کند تا در نهایت به یک آرایهٔ مرتب‌شده برسد. مثالی از این مرتب‌سازی را در تصویر مشاهده می‌کنید.

کاربرد دیگر این الگوریتم در مرتب‌سازی شکیبانه است. این مرتب‌سازی که در واقع از یک بازی کارتی گرفته شده‌است، به این گونه عمل می‌کند: فرض کنید $n$ کارت با شماره‌های یک تا $n$ با ترتیبی دلخواه داریم. اولین کارت را روی میز قرار داده و اولین کپه کارت را می‌سازیم. بعد از آن در هر مرحله، کارت جدید یا به چپ‌ترین کپه‌ای اضافه می‌شود که کارت سر آن کپه دارای عددی بزرگتر یا مساوی عدد کارت جدید باشد یا در راست همهٔ کپه‌ها به عنوان کپه‌ای جدید قرار می‌گیرد. در این صورت بعد از تمام شدن کارت‌ها، تعدادی کپه کارت داریم که در هر کپه اعداد کارت از پایین کپه به بالا نزولی‌اند و کافیست برای مرتب‌سازی کل کارت‌ها این کپه‌ها را باهم ادغام کنیم. (ادغام $k$ لیست)

از این الگوریتم در مرتب‌سازی خارجی نیز استفاده می‌شود. از مرتب‌سازی خارجی برای مرتب کردن اطلاعات فایل‌ها هنگامی که حافظهٔ اصلی یا RAM محدود است، بهره می‌گیریم. این گونه عمل می‌کنیم که در هر مرحله مقداری از فایل که در حافظهٔ اصلی می‌تواند قرار گیرد را برداشته، توسط یک الگوریتم مرتب‌سازی، مرتب نموده و در حافظهٔ خارجی مثلاً Hard Drive قرار می‌دهیم. در نهایت بخش‌های مرتب‌شدهٔ فایل را باهم ادغام می‌کنیم.