Մասնակից:Ashikyan H.

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

Հաջորդական դասավորությունը ոչ նվազող կամ ոչ բարձրացվող հաջորդականություն է։ Բիտոնիկ տեսակավորումը դասավորում է, որը ունի $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]

External links

• A discussion of this algorithm
• Reference code at NIST
• Tutorial with animated pictures and working code
• Experimental Analysis of Parallel Sorting Algorithms