Битоник сортирање

Битоник сортирање

Битоник сортирајућа мрежа са 8 улаза.
Класа	Алгоритам за сортирање
Структура података	[Низ]
Најгора перформанца	$O(\log(n)^{2})$ параллел тиме
Најбоља перформанца	$O(\log(n)^{2})$ параллел тиме
Просечна перформанца	$O(\log(n)^{2})$ параллел тиме
Најгора просторна комплексност	$O(n\log(n)^{2})$ цомпараторс

Битоник мергесорт је паралелни алгоритам за сортирање. Користи се такође као и механизам за прављење сортирајућих мрежа. Алгоритам је развио Кен Бечер. Новонастала сортирајућа мрежа има  О(нлог(н)^2) компаратора, и дубину која је О(\лог(н)^2) где је н број бројева које треба сортирати.

Како ради алгоритам

Следи битоник сортирајућа мрежа са 16 улаза.

Ових 16 бројева улазе са леве стране, крећу се по жицама и излазе на десној страни. Мрежа је дизајнирана да сортира елементе тако што је највећи члан скроз доле.

Стрелице су компаратори. Када год два броја дођу до краја стрлице, пореде се да би се осигурало да стрелица показује на већи број. Ако није то случај, места им мењају места. 

Сваки црвени квадрат има исту структуру: сваки улз са горње половине се пореди са одговарајућим улазом из доње половине, са свим стрелицама да показују доле (тамно црвено) или горе (светло црвено). Ако се деси да улази праве битоник секвенцу онда ће излаз формирати две секвенце. I доња и горња половина ће бити битоник, са сваким елементом на горњој половини мањим или једнаким у односу на сваки елемент на доњој половини. Ова теорема није тривијална, али се може проверити пажљивом провером свих случајева поређења разних улаза помоћу нула-један принципа.

Црвени правоугаоници се комбинују и праве плаве или зелене правоугаонике. Сваки правоугаоник има исту структуру: црвени правоугаоник се примењује на целу улазну секвенцу, па на сваку половину резултата, па на сваку половину половине резултата итд. Све стрелице показују на доле (плаво) или на горе (зелено). Ова структура је позната као и лептирова мрежа. Ако се улаз у правоугаоник задеси да буде битоник, онда ће цео излаз бити сортиран растуће или опадајуће. Ако број уђе у у зелени или плави правоугаоник, онда ће први црвени правоугаоник да сортира у исправну половину. Онда ће проћи кроз мањи правоугаоник који ће сортирати у исправну четвртину итд. Ово се наставља док елемент није на тачној позицији. Тако ће излаз из плавог или црвеног правоугаоника бити потпуно сортиран.

Плави и црвени правоугаоници се комбинују да формирају целу сортирајућу мрежу. За произвољну секвенцу улаза, сортираће их исправно, са највећим елементом на дну. Излаз сваког зеленог или плавог правоугаоника ће бити сортирана секвенца, и тако ће излаз за сваки пар бити низова бити битоник, јер је горњи правоугаоник плав, а доњи зелен. Свакој колони зелених или плавих правоугаоника треба н сортираних секвенци које се деле на парове где настају н/2 битоник секвенци, које се онда сортирају по правоугаоницима у тој колони да би настале н/2 сортиране секвенце. Пошто је последња фаза била плава највећи елемент ће бити на дну.  

Алтернативне репрезентације

Сваки зелени правоугаоник обавља посао као и плави, само сортирају супротно. Зато би сваки зелени правоугаоник могао бити замењен плавим тако што би се све жице помериле на супротну страну. Ово би омогућило свим стрелицама да показују на исту страну, али би онемогућило хоризонталним линијама да буду праве. Ипак, слична замене би могла да се спроведе до доње десне половине излаза из било ког црвеног правоугаоника и сортирање би и даље било исправно јер је инверз битоник секвенце и даље битоник. Зато је следећи дијаграм еквивалентан оном изнад:

Стрелице нису морале бити приказене јер сваки компаратор сортира у истом правцу. Плави и црвени правоугаоници имају исту сврху као и на пређашњем дијаграму. Нарандзасти провоугаоник је еквивалентан црвеном где је секвенца обрнута за доњу половину својих улаза и доњу половину излаза. Ово је најчешћи приказ битоник сортирајуће мреже.

Пример кода

Следи имплементација за битоник мергесорт алгоритам у Пyтхон-у. Улаз је Боолеан вредност уп, а низ x дужине степена 2. Излаз је сортиран низ који расте ако је уп труе, а опада ако је фалсе.

def bitonic_sort(up, x):
    if len(x) <= 1:
        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) == 1:
        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 BitonicSort {
    static void kernel(int[] a, final int p, final int q) {
        final int d = 1 << (p-q);

        for(int i=0;i<a.length;i++) {
            boolean up = ((i >> p) & 2) == 0;

            if ((i & d) == 0 && (a[i] > a[i | d]) == up) {
                int t = a[i]; a[i] = a[i | d]; a[i | d] = t;
            }
        }
    }

    static void bitonicSort(final int logn, int[] a) {
        assert a.length == 1 << logn;

        for(int i=0;i<logn;i++) {
            for(int j=0;j<=i;j++) {
                kernel(a, i, j);
            }
        }
    }

    public static void main(String[] args) {
        final int logn = 5, n = 1 << logn;

        int[] a0 = new int[n];
        for(int i=0;i<n;i++) a0[i] = (int)(Math.random() * 1000);

        for(int k=0;k<a0.length;k++) System.out.print(a0[k] + " ");
        System.out.println();

        bitonicSort(logn, a0);

        for(int k=0;k<a0.length;k++) System.out.print(a0[k] + " ");
        System.out.println();
    }
}

Спољашње везе

• А дисцуссион оф тхис алгоритхм Архивирано на сајту Wayback Machine (10. јануар 2017)
• Референце цоде ат НИСТ
• Туториал wитх аниматед пицтурес анд wоркинг цоде