مرتب‌ساز بایتونیک

مرتب‌ساز ادغامی بایتونیک الگوریتمی موازی برای مرتب‌سازی است که از آن برای ساخت شبکه‌های مرتب‌سازی نیز استفاده می‌شود. این الگوریتم را کِن بچر (ken batcher) ابداع کرده‌است. شبکه‌های مرتب‌سازی به دست آمده از $O(nlog(n)^{2})$ مقایسه‌کننده تشکیل شده و تأخیری به میزان $O(log(n)^{2})$ دارند که n تعداد مواردی است که باید مرتب شوند.

توالی مرتب‌شده یک توالی یکنواخت غیر کاهشی (یا غیر افزایشی) است. توالی بایتونیک توالی‌ای با $x_{0}$ ≤ … ≤ $x_{k}$ ≥ … ≥ $x_{n-1}$ برای برخی مقادیر k، که مقادیر آن در محدوده ۰ ≤ k <n قرار دارند، یا شیفت دورانی این توالی است.

الگوریتم چگونه کار می‌کند

آنچه در ادامه می‌آید یک شبکهٔ مرتب‌سازی با ۱۶ ورودی است:

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

فلش‌ها همان مقایسه‌کننده‌ها هستند. هرگاه دو عدد به دو انتهای یک فلش می‌رسند، با یکدیگر مقایسه شده تا تضمین شود که فلش به سمت عدد بزرگتر اشاره دارد. چنانچه بدون ترتیب باشند، جایشان با یکدیگر عوض می‌شود. جعبه‌های رنگی تنها برای ترسیم هستند و تأثیری بر الگوریتم ندارند.

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

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

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

کد نمونه

آنچه در ادامه می‌آید پیاده‌سازی الگوریتم مرتب‌سازی ادغامی بایتونیک در پایتون است. ورودی مقدار بولی up و لیست x طولی از توان ۲ دارد. خروجی لیستی مرتب‌شده‌است که اگر up برقرار باشد صعودی و در غیر این صورت نزولی است.

  def bitonic_sort(up, x):
    if len(x) <= ۱:
      return x
    else:
      first = bitonic_sort(True, x[:len(x) / 2])
      second = bitonic_sort(False, x[len(x) / 2:])
      return bitonic_merge(up, first + second)
  def bitonic_merge(up, x):
    # assume input x is bitonic, and sorted list is returned
    if len(x) == ۱:
      return x
    else:
      bitonic_compare(up, x)
      first = bitonic_merge(up, x[:len(x) / 2])
      second = bitonic_merge(up, x[len(x) / 2:])
      return first + second
  def bitonic_compare(up, x):
    dist = len(x) / 2
    for i in range(dist):
      if (x[i]> x[i + dist]) == up:
        x[i], x[i + dist] = x[i + dist], x[i] #swap

>>> bitonic_sort(True, [10, 30, 11, 20, 4, 330, 21, 110])

 [4, 10, 11, 20, 21, 30, 110, 330]

>>> bitonic_sort(False, [10, 30, 11, 20, 4, 330, 21, 110])

 [330, 110, 30, 21, 20, 11, 10, 4]

در ادامه نیز پیاده‌سازی دیگری در جاوا آمده‌است.

public class BitonicSorter implements Sorter
{
    private int[] a;
    // sorting direction:
    private final static boolean ASCENDING=true, DESCENDING=false;

    public void sort(int[] a)
    {
        this.a=a;
        bitonicSort(0, a.length, ASCENDING);
    }

    private void bitonicSort(int lo, int n, boolean dir)
    {
        if (n>1)
        {
            int m=n/2;
            bitonicSort(lo, m, ASCENDING);
            bitonicSort(lo+m, m, DESCENDING);
            bitonicMerge(lo, n, dir);
        }
    }

    private void bitonicMerge(int lo, int n, boolean dir)
    {
        if (n>1)
        {
            int m=n/2;
            for (int i=lo; i<lo+m; i++)
                compare(i, i+m, dir);
            bitonicMerge(lo, m, dir);
            bitonicMerge(lo+m, m, dir);
        }
    }

    private void compare(int i, int j, boolean dir)
    {
        if (dir==(a[i]>a[j]))
            exchange(i, j);
    }

    private void exchange(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

    public static void main(String[] args) {
      Sorter s = new BitonicSorter();
      s.sort(b);
    }

}    // end class BitonicSorter

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

public class BitonicSorterForArbitraryN implements Sorter
{
    private int[] a;
    private final static boolean ASCENDING=true;    // sorting direction

    public void sort(int[] a)
    {
        this.a=a;
        bitonicSort(0, a.length, ASCENDING);
    }

    private void bitonicSort(int lo, int n, boolean dir)
    {
        if (n>1)
        {
            int m=n/2;
            bitonicSort(lo, m, !dir);
            bitonicSort(lo+m, n-m, dir);
            bitonicMerge(lo, n, dir);
        }
    }

    private void bitonicMerge(int lo, int n, boolean dir)
    {
        if (n>1)
        {
            int m=greatestPowerOfTwoLessThan(n);
            for (int i=lo; i<lo+n-m; i++)
                compare(i, i+m, dir);
            bitonicMerge(lo, m, dir);
            bitonicMerge(lo+m, n-m, dir);
        }
    }

    private void compare(int i, int j, boolean dir)
    {
        if (dir==(a[i]>a[j]))
            exchange(i, j);
    }

    private void exchange(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

    private int greatestPowerOfTwoLessThan(int n)
    {
        int k=1;
        while (k<n)
            k=k<<1;
        return k>>1;
    }

    public static void main(String[] args) {
      Sorter s = new BitonicSorterForArbitraryN();
      s.sort(b);
    }

}

منابع

Batcher odd–even mergesort

Bitonic sorting network for n not a power of 2 بایگانی‌شده در ۴ دسامبر ۲۰۱۶ توسط Wayback Machine

Bitonic sort بایگانی‌شده در ۱۰ ژانویه ۲۰۱۷ توسط Wayback Machine

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

Wikipedia contributors, "Bitonic sorter," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/w/index.php?title=Bitonic_sorter&oldid=717351506 (accessed May 3, 2016).