مرتب‌سازی مسابقه‌ای

مرتب‌سازی مسابقه‌ای

رده	الگوریتم مرتب‌سازی
ساختمان داده	درخت برنده (آرایه)
کارایی بدترین حالت	$O(n\log n)$
کارایی متوسط	$O(n\log n)$
پیچیدگی فضایی	$O(n)$

مرتب‌سازی مسابقه‌ای (به انگلیسی: Tournament sort) یک الگوریتم مرتب‌سازی است. این الگوریتم مرتب‌سازی انتخابی ساده را با استفاده از یک صف اولویت‌دار یا یک درخت برنده برای پیدا کردن عنصر بعدی در مرتب‌سازی بهبود می‌بخشد. در مرتب‌سازی انتخابی ساده، $O(n)$ عمل صورت می‌گیرد تا عنصر بعدی از $n$ عنصر را انتخاب کند؛ در یک مرتب‌سازی مسابقه‌ای، $O(\log n)$ عمل صورت می‌گیرد (پس از ساختن مسابقه ابتدایی در $O(n)$). مرتب‌سازی مسابقه‌ای یک تنوع از مرتب‌سازی هرمی است.

پیاده‌سازی با درخت برنده

پیاده‌سازی مرتب‌سازی مسابقه‌ای با درخت برنده

درخت برنده نوعی درخت مسابقه است که از $n$ راس خارجی و $n-1$ راس داخلی تشکیل می‌شود. رئوس خارجی نمایندهٔ بازیکنان و رئوس داخلی هر کدام نمایندهٔ یک تک‌مسابقه بین دو بازیکن است. در درخت برنده هر راس داخلی باید بازیکن برنده بین دو راس فرزند خود را ذخیره کند و در انتها ریشه درخت حاوی بازیکنی خواهد بود که در تمام تک‌مسابقه‌ها برنده شده‌است.
اگر برنده را در هر تک‌مسابقه بازیکنی در نظر بگیریم که مقدار آن کمتر است؛ در این صورت ریشه درخت اشاره به بازیکنی خواهد داشت که کمترین مقدار را بین تمام بازیکنان دارد. با طراحی چنین داده ساختاری می‌توان الگوریتم مرتب‌سازی مسابقه‌ای را اجرا نمود. اگر آرایه مورد نظر برای مرتب‌سازی دارای $k$ عنصر باشد؛ درخت مسابقه‌ای با $n$ راس خارجی ($n$ اولین عدد توان ۲ است که بزرگتر یا مساوی $k$ باشد) و $n-1$ راس داخلی می‌سازیم. رئوس خارجی به ترتیب به عناصر آرایه اشاره می‌کنند و رئوس خارجی اضافه نیز به هیچ خانه‌ای اشاره ندارند. رئوس داخلی درخت از پایین به بالا به برنده هر تک‌مسابقه اشاره می‌کنند تا زمانی که ریشه مشخص کنندهٔ برندهٔ نهایی شود. برندهٔ نهایی را به عنوان کوچکترین عنصر در ابتدای یک آرایهٔ جدید می‌گذاریم و راس خارجی که به آن اشاره داشت را از دور مسابقات حذف می‌کنیم. در مسیر رسیدن آن راس به ریشه مسابقات را تکرار می‌کنیم تا برندهٔ نهایی را با نبود راس برندهٔ دور قبل شناسایی کنیم. آن‌قدر به این کار ادامه می‌دهیم تا تمام بازیکنان از مسابقات حذف شوند. در این مرحله آرایهٔ ساخته‌شده مرتب خواهد بود.

زمان اجرا و پیچیدگی فضایی الگوریتم

زمان اجرای این الگوریتم به دو قسمت تقسیم می‌شود. به اندازه $O(n)$ طول می‌کشد که بازیکنان در رئوس خارجی قرار گیرند و به اندازه $O(n)$ نیز طول می‌کشد تا درخت برنده تکمیل شده و برندهٔ نهایی مشخص شود. سپس در هر عمل حذف بازیکن از مسابقات به اندازه $O(\log n)$ طول می‌کشد تا درخت برنده بازسازی شود. $n$ مرتبه این عمل انجام می‌شود تا در نهایت آرایه مرتب شود. پس در مجموع زمان اجرای این الگوریتم از $O(n\log n)$ می‌شود.
مقدار حافظه لازم برای این الگوریتم متشکل است از آرایهٔ اولیه و آرایهٔ مرتب شده و یک درخت مسابقه که تعداد رئوس خارجی آن از ۲ برابر تعداد بازیکنان کمتر است. در درخت مسابقه تعداد رئوس داخلی همیشه یکی کمتر از تعداد رئوس خارجی است. پس در کل پیچیدگی فضایی این الگوریتم از $O(n)$ است.

پیاده‌سازی به زبان پایتون

مرتب‌سازی مسابقه‌ای با استفاده از درخت برنده (آرایه) در زبان برنامه‌نویسی پایتون به صورت زیر پیاده‌سازی می‌شود. در این پیاده‌سازی از مفهوم هرم کمینه، که نوعی هرم دودویی است، استفاده شده که در آن هر راس با اندیس $k$ در آرایه، پدر دو راس با اندیس‌های $2k$ و $2k+1$ است. به همین دلیل تعداد رئوس زائد بالا می‌رود و اندازه کل آرایه می‌تواند تا ۴ برابر تعداد اعضای آرایه اولیه افزایش یابد؛ اما به هر صورت پیچیدگی فضایی آن از $O(n)$ است.

import math
def build(A, B, x, l, r):
    if l == r:
        B[x] = (A[l], x)
    else:
        mid = (l + r) // 2
        build(A, B, 2 * x, l, mid)
        build(A, B, (2 * x) + 1, mid + 1, r)
        if B[(2 * x) + 1][0] < B[2 * x][0]:
            B[x] = B[(2 * x) + 1]
        else:
            B[x] = B[2 * x]

def pop(B):
    result = B[1][0]
    index = B[1][1]
    B[index] = None
    while index > 1:
        index = index // 2
        if B[index * 2] is None:
            minimum = B[(index * 2) + 1]
        elif B[(index * 2) + 1] is None:
            minimum = B[index * 2]
        else:
            minimum = min(B[index * 2], B[(index * 2) + 1])
        if minimum == B[index]:
            break
        B[index] = minimum
    return result

A = [-8, 3, 17, 57, 0, -19, 21, 5, 965 , 2, 0, 1, 34, 83]
n = len(A)
B = [None] * (2 ** (math.ceil(math.log2(n)) + 1))
build(A, B, 1, 0, n - 1)
sorted_array = [pop(B) for _ in range(n)]
print(sorted_array)

جستارهای وابسته

• مرتب‌سازی هرمی
• الگوریتم مرتب‌سازی
• مرتب‌سازی انتخابی
• هرم (علوم رایانه)
• درخت مسابقه

منابع

Donald Knuth, The Art of Computer Programming, Sorting and Searching, Volume 3, 1973.
Stepanov, Alexander and Aaron Kershenbaum. Using Tournament Trees to Sort, Brooklyn: Center for Advanced Technology in Telecommunications, 1986.
https://www.cise.ufl.edu/~sahni/cop3530/slides/lec252.pdf