مرتب‌سازی ادغامی دسته‌ای فرد–زوج

مرتب‌سازی ادغامی دسته‌ای فرد–زوج

مرتب‌سازی ادغامی دسته‌ای فرد–زوج

تجسم مرتب‌سازی ادغامی دسته‌ای فرد-زوج با هشت ورودی.
رده	الگوریتم مرتب‌سازی
ساختمان داده	آرایه
کارایی بدترین حالت	$O(\log ^{2}(n))$ زمان موازی
کارایی بهترین حالت	$O(\log ^{2}(n))$ زمان موازی
کارایی متوسط	$O(\log ^{2}(n))$ زمان موازی
پیچیدگی فضایی	$O(n\log ^{2}(n))$ مقایسه‌گرها

Visualization of the odd–even mergesort network with eight inputs

معرفی

مرتب‌سازی ادغامی دسته‌ای فرد–زوج یک ساز و کار عمومی برای مرتب‌سازی شبکه‌هاست. این روش توسط کِن بچر ابداع شده است.

اگر تعداد عناصری که می خواهیم مرتب کنیم n باشد اندازه (تعداد مقایسه کننده‌های استفاده شده) این الگوریتم nlog^۲n و عمق (حداکثر تعداد مقایسه کننده‌هایی که در مسیر یک ورودی به خروجی قرار دارند) آن log^۲n است.

هرچند که مقایسه خوبی نیست اما دانلد_کنوت در سال ۱۹۹۸ به این نتیجه رسید که روش دسته‌ای نسبت به روش شبکه AKS بهتر است مگر اینکه n بیش از کل ظرفیت حافظه رایانه‌های روی زمین باشد.

این الگوریتم به عنوان یکی از ساده‌ترین راه‌ها برای انجام مرتب‌سازی‌های منطقی بهینه بر روی انواع سخت‌افزارهای پردازش گرافیکی انجام پذیر است.

نمونه کد

یک نمونه پیاده‌سازی از این الگوریتم به زبان پایتون در زیر آمده است. ورودی آن یک لیست x به طول توانی از ۲ است.

def compare_and_swap(x، a، b):
    if x[a]> x[b]:
        x[a], x[b] = x[b], x[a]

def oddeven_merge(x، lo، hi، r):
    step = r * 2
    if step <hi - lo:
        oddeven_merge(x, lo, hi, step)
        oddeven_merge(x, lo + r, hi, step)
        for i in range(lo + r, hi - r, step):
            compare_and_swap(x, i, i + r)
    else:
        compare_and_swap(x, lo, lo + r)

def oddeven_merge_sort_range(x، lo، hi):
    """ sort the part of x with indices between lo and hi.

    Note: endpoints (lo and hi) are included.
    """
    if (hi - lo)>= 1:
        # if there is more than one element, split the input
        # down the middle and first sort the first and second
        # half, followed by merging them.
        mid = lo + ((hi - lo) / 2)
        oddeven_merge_sort_range(x, lo, mid)
        oddeven_merge_sort_range(x, mid + 1, hi)
        oddeven_merge(x, lo, hi, 1)

def oddeven_merge_sort(x):
    oddeven_merge_sort_range(x, 0, len(x)-1)

>>> data = [۴، ۳، ۵، ۶، ۱، ۷، ۸]
>>> oddeven_merge_sort(data)
>>> data
[۱، ۲، ۳، ۴، ۵، ۶، ۷، ۸]

منابع

1. http://en.wikipedia.org/w/index.php?title=Batcher_odd–even_mergesort&oldid=450869165
2. D.E. Knuth. The Art of Computer Programming، Volume 3: Sorting and Searching، Third Edition. Addison-Wesley، ۱۹۹۸. ISBN 0-201-89685-0. Section 5.3.4: Networks for Sorting، pp. ۲۱۹–۲۴۷.
3. https://web.archive.org/web/20111205010757/http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter46.html

پیوند به بیرون

• Odd–even mergesort at fh-flensburg.de