پرش به محتوا

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

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

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

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

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

[ویرایش]
برگرفته از «https://fa.wikipedia.org/w/index.php?title=مرتب‌سازی_ادغامی_دسته‌ای_فرد–زوج&oldid=31491701»