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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
مرتب‌سازی ادغامی دسته‌ای فرد–زوج
تجسم مرتب‌سازی ادغامی دسته‌ای فرد-زوج با هشت ورودی.
تجسم مرتب‌سازی ادغامی دسته‌ای فرد-زوج با هشت ورودی.
کلاس الگوریتم مرتب‌سازی
داده ساختار آرایه
بدترین زمان اجرا 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

معرفی[ویرایش]

مرتب سازی ادغامی دسته ای فرد-زوج یک ساز و کار عمومی برای مرتب سازی شبکه هاست. این روش توسط کِن بچر(ken batcher) ابداع شده است.

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

هرچند که مقایسه خوبی نیست اما کنوث (knuth) در سال ۱۹۹۸ به این نتیجه رسید که روش دسته ای نسبت به روش شبکه 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%E2%80%93even_mergesort&oldid=450869165
  2. D.E. Knuth. The Art of Computer Programming، Volume ۳: Sorting and Searching، Third Edition. Addison-Wesley، ۱۹۹۸. ISBN ۰-۲۰۱-۸۹۶۸۵-۰. Section ۵.۳.۴: Networks for Sorting، pp. ۲۱۹–۲۴۷.
  3. http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter46.html

پیوند به بیرون[ویرایش]