Bitonik sortiranje

Bitonik sortiranje

Bitonik sortirajuća mreža sa 8 ulaza.
Klasa	Algoritam za sortiranje
Struktura podataka	[Niz]
Najgora performanca	$O(\log(n)^{2})$ parallel time
Najbolja performanca	$O(\log(n)^{2})$ parallel time
Prosečna performanca	$O(\log(n)^{2})$ parallel time
Najgora prostorna kompleksnost	$O(n\log(n)^{2})$ comparators

Bitonik mergesort je paralelni algoritam za sortiranje. Koristi se takođe kao i mehanizam za pravljenje sortirajućih mreža. Algoritam je razvio Ken Bečer. Novonastala sortirajuća mreža ima  O(nlog(n)^2) komparatora, i dubinu koja je O(\log(n)^2) gde je n broj brojeva koje treba sortirati.

Kako radi algoritam

Sledi bitonik sortirajuća mreža sa 16 ulaza.

Ovih 16 brojeva ulaze sa leve strane, kreću se po žicama i izlaze na desnoj strani. Mreža je dizajnirana da sortira elemente tako što je najveći član skroz dole.

Strelice su komparatori. Kada god dva broja dođu do kraja strlice, porede se da bi se osiguralo da strelica pokazuje na veći broj. Ako nije to slučaj, mesta im menjaju mesta. 

Svaki crveni kvadrat ima istu strukturu: svaki ulz sa gornje polovine se poredi sa odgovarajućim ulazom iz donje polovine, sa svim strelicama da pokazuju dole (tamno crveno) ili gore (svetlo crveno). Ako se desi da ulazi prave bitonik sekvencu onda će izlaz formirati dve sekvence. I donja i gornja polovina će biti bitonik, sa svakim elementom na gornjoj polovini manjim ili jednakim u odnosu na svaki element na donjoj polovini. Ova teorema nije trivijalna, ali se može proveriti pažljivom proverom svih slučajeva poređenja raznih ulaza pomoću nula-jedan principa.

Crveni pravougaonici se kombinuju i prave plave ili zelene pravougaonike. Svaki pravougaonik ima istu strukturu: crveni pravougaonik se primenjuje na celu ulaznu sekvencu, pa na svaku polovinu rezultata, pa na svaku polovinu polovine rezultata itd. Sve strelice pokazuju na dole (plavo) ili na gore (zeleno). Ova struktura je poznata kao i leptirova mreža. Ako se ulaz u pravougaonik zadesi da bude bitonik, onda će ceo izlaz biti sortiran rastuće ili opadajuće. Ako broj uđe u u zeleni ili plavi pravougaonik, onda će prvi crveni pravougaonik da sortira u ispravnu polovinu. Onda će proći kroz manji pravougaonik koji će sortirati u ispravnu četvrtinu itd. Ovo se nastavlja dok element nije na tačnoj poziciji. Tako će izlaz iz plavog ili crvenog pravougaonika biti potpuno sortiran.

Plavi i crveni pravougaonici se kombinuju da formiraju celu sortirajuću mrežu. Za proizvoljnu sekvencu ulaza, sortiraće ih ispravno, sa najvećim elementom na dnu. Izlaz svakog zelenog ili plavog pravougaonika će biti sortirana sekvenca, i tako će izlaz za svaki par biti nizova biti bitonik, jer je gornji pravougaonik plav, a donji zelen. Svakoj koloni zelenih ili plavih pravougaonika treba n sortiranih sekvenci koje se dele na parove gde nastaju n/2 bitonik sekvenci, koje se onda sortiraju po pravougaonicima u toj koloni da bi nastale n/2 sortirane sekvence. Pošto je poslednja faza bila plava najveći element će biti na dnu.  

Alternativne reprezentacije

Svaki zeleni pravougaonik obavlja posao kao i plavi, samo sortiraju suprotno. Zato bi svaki zeleni pravougaonik mogao biti zamenjen plavim tako što bi se sve žice pomerile na suprotnu stranu. Ovo bi omogućilo svim strelicama da pokazuju na istu stranu, ali bi onemogućilo horizontalnim linijama da budu prave. Ipak, slična zamene bi mogla da se sprovede do donje desne polovine izlaza iz bilo kog crvenog pravougaonika i sortiranje bi i dalje bilo ispravno jer je inverz bitonik sekvence i dalje bitonik. Zato je sledeći dijagram ekvivalentan onom iznad:

Strelice nisu morale biti prikazene jer svaki komparator sortira u istom pravcu. Plavi i crveni pravougaonici imaju istu svrhu kao i na pređašnjem dijagramu. Narandzasti provougaonik je ekvivalentan crvenom gde je sekvenca obrnuta za donju polovinu svojih ulaza i donju polovinu izlaza. Ovo je najčešći prikaz bitonik sortirajuće mreže.

Primer koda

Sledi implementacija za bitonik mergesort algoritam u Python-u. Ulaz je Boolean vrednost up, a niz x dužine stepena 2. Izlaz je sortiran niz koji raste ako je up true, a opada ako je false.

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]

Sledi implementacija u Javi

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();
    }
}

Spoljašnje veze

• A discussion of this algorithm Архивирано на сајту Wayback Machine (10. јануар 2017)
• Reference code at NIST
• Tutorial with animated pictures and working code