Բիտոնիկ տեսակավորող

Բիտոնիկ տեսակավորող, զուգահեռ ալգորիթմ է տեսակավորման համար։ Այն նաև օգտագործվում է շինարարության մեջ ցանցի տեսակավորման համար։ Ալգորիթմը ստեղծել է Քեն Բատչերը. Արդյունքում տեսակավորման ցանցերը բաղկացած են O(n log²(n)) comparators and have a delay of O(log²(n)), where n is the number of items to be sorted.

Բիտոնիկ տեսակավորող
Տեսակ	parallel algorithm? և տեսակավորման ալգորիթմ
Տվյալների կառուցվածք	$O(n\log ^{2}(n))$
Վատագույն դեպքում կատարումը	$O(\log ^{2}(n))$
Լավագույն դեպքում կատարումը	$O(\log ^{2}(n))$
Օգտագործում է	զանգված
Հայտնաբերող	Kenneth Edward Batcher?

Հաջորդական դասավորությունը ոչ նվազող, կամ հաջորդականություն է։ Բիտոնիկ տեսակավորումը դասավորում է, որը ունի $x_{0}\leqq \ldots \leqq x_{k}\geqq \ldots \geqq x_{n-1}$ for some $k,0\leqq k<n$, կամ շրջանաձև հերթափոխություն ունեցող տեսակավորում է։

Ինչպես է գործում ալգորիթմը

Սրանք 16 միջոցներն են բիտոնիկ տեսակավորման համար։

16 համարները սկիզբ են առնում մուտքի ձախ վերջնահատվածից, սահելով դասավորվում են յուրաքանչյուր 16 հորիզոնական լարի առջև և դուրս են գալիս աջ կողմի ելքից։ Համացանցը նախագծված է տեսակավորելու միավորները ըստ աճման արժեքի։ Աղեղները համեմատության բացարձակ արժեքներ են։ Երբ երկու թվերը հասնում են աղեղների երկու վերջավորությանը, դրանք համեմատվում են հաստատելու, որ աղեղները ուղղված են դեպի խոշորագույն թիվը։ Եթե դրանք շարքից դուրս են գալիս, ապա փոխարինվում են։ Գունավոր արկղերը պատկերավորության համար են և ոչ մի ազդեցություն չունեն ալգորիթմի վրա։

Յուրաքանչյուր կարմիր արկղ ունի միևնույն կառուցվածքը, վերին կեսի յուրաքանչյուրը մուտքը համեմատվում է համապատասխան կենտրոնական մուտքին՝ բոլոր աղեղները ուղղելով ներքև (մուգ կարմիր) կամ վերև (բաց կարմիր)։ Եթե մուտքերը ձևավորում են բիտոնիկ միասնություն, ապա ելքերը նույնպես կձևավորեն երկու բիտոնիկ միասնություն։ Եթե ելքի վերին կեսը բիտոնիկ է, ինչպես նաև կենտրոնական հատվածը, ապա վերին հատվածի արժեքները դասավորվում են բարձրագույնից դեպի ցածրագույն կամ հավասարազոր կենտրոնական կեսին և հակառակը։ Թեորիան ակնհայտ չէ, բայց ապացուցելի է, եթե ուշադրությամբ քննվեն այն բոլոր դեպքերը, երբ տարբեր մուտքերը կարող են համեմատվել օգտագործելով զերո – մեկ կանոնը։

Կարմիր արկղերը միավորվում են ձևավորելու կանաչ և կապույտ արկղեր։ Այսպիսի ցանկացած արկղ ունի նույն կառուցվածքը և աշխատում է վերոնշյալ համակարգով։ Այս կառուցվածքը հայտնի է թիթեռնիկի համացանց անվամբ։ Այն ենթարկվում է նույն բիտոնիկ միասնության կանոնին։ Եթե թիվը մտնում է կապույտ կամ կանաչ արկղը, ապա առաջինն կարմիր արկղը կտեսակավորի այն ճիշտ կողմի վրա։ Այս գործընթացը շարունակվում է այնքան, մինչև որ համակարգվի համապատասխան ճիշտ տեղերում։ Այսպիսով կանաչ կամ կապույտ արկղի ելքերը ամբողջովին համակարգվում են։.

Կանաչ և կապույտ արկղերը միավորվում են, որպեսզի ձևավորեն ամբողջական տեսակավորման համակարգը։ Ցանկացած մուտքերի կամայական հերթականությունը կտեսակավորվի ճշգրտորեն՝ բարձրագույն արժեքը կենտրոնում։ Այս հատկանիշը ակնհայտ է։ Ցանկացած կանաչ կամ կապուտ արկղի ելքը կտեսակավորվի հերթականությամբ, այսպիսով բոլոր ելքերը կլինեն դասավորված իրարամերձ հատվածներում ստեղծելով բիոտոնիկ կապ, քանի որ վերևում կգտնվի կապույտ արկղը, իսկ կենտրոնականումհատվածում՝ կանաչը։ Կապույտ և կանաչ արկղերի յուրաքանչյուր սյունակ ձևավորում է N տեսակավորված համակցություն և շղթայում այն զույգերով՝ ձևավորելով N/2 բիտոնիկ համակցություն, որը հետագայում տեսակավորվում է ըստ արկղերի սյունակների, որպեսզի ձևավորվի N/2 բիտոնիկ համատեղություն։ Այս պրոցեսը սկսվում է, երբ յուրաքանչյուր մուտք դիտարկվում է որպես մեկ էլէմենտի տեսակավորված մասնիկ, և ընթանում է բոլոր սյունակների միջով մինչև որ վերջինս միավորի այն, որպես մեկ միասնական տեսակավորված ցանկ։ Վերջնական էտապը եզրափակվում է կապույտով, ուստի այս վերջնական ցուցակը կունենա ամենախոշորագույն մասնիկը կենտրոնական հատվածում։

Յուրաքանչյուր կանաչ արկղ կատարում է նույն գործողությունն, ինչ կապույտը, սակայն տեսակավորվում է հակառակ ուղղությամբ։ Այսպիսով ցանկացած կանաչ արկղ կարող է փոխարինվել կապույտով, եթե այն կատարվի խաչաձև միացումով, որտեղ բոլոր լարերը տեղակայվում են հակառակ ուղղությամբ։ Սա թույլ կտա, որ բոլոր աղեղներն ուղղված լինեն մեկ ուղղությամբ, բայց հորիզոնական գծերը ուղիղ չեն լինի։ Այնուամենայնիվ նմանատիպ խաչաձևումը կարող է տեղադրվել կարմիր բլոկի աջ կենտրոնական ելքային հատվածում և տեսակավորումը միևնույնն է ճշգրիտ կկատարվի, քանի որ բիտոնիկ միակցության հակադրությունը նույնպես բիտոնիկ է։ Եվ եթե կարմիր արկղն ունի խաչաձևում իրենից առաջ և հետո, ապա այն կարող է վերադասավորվել ներքուստ այնպես, որ խաչաձևումերը զրոյականանան, այսպիսով լարերը կրկին ուղիղ կդառնան։ Այսպիսով այս դիագրամը հավասարազոր է վերոնշյալին, որտեղ յուրաքանչյուր կանաչ արկղ դա կապույտն է գումարած խաչաձևումը, և ցանկացած նարնջագույն արկղ կարմիր արկղ է իրենից ներկայացնում, որը համատեղում է այսպիսի երկու խաչաձևումեր։

Աղեղների գլուխները չեն պատկերվում, քանզի ցանկացած կոմպարատոր տեսակավորվում է միևնույն ուղղությամբ։ Կապույտ և կարմիր բլոկերը կատարում են միևնույն գործողությունը, ինչ նախկինում։ Նարնջագույն բլոկերը համարժեք են կարմիրին, որտեղ տեսակավորման հերթականությունը հակադարձ է իր կենտրոնական կեսի մուտքերին և ելքերին։ Սա բիտոնիկ տեսակավորման համացանցի ամենատարածված պատկերումն է։

Կոդի օրինակ

Վերոնշյալը բիտոնիկ տեսակավորման ալգորիթմի իրականացումն է Python Մուտքը վերին բուլյան արժեքն է և X ցանկի ուժի լայնությունն երկուսում։ Ելքը տեսակավորված ցանկ է, որը աճում է եթե վերին արժեքը ճշգրիտ է և պակասում է հակառակ պարագայում։

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]