Կենտ-զույգ տեսակավորում

Վիքիպեդիայից՝ ազատ հանրագիտարանից

Կաղապար:Infobox Algorithm

Example of odd-even transposition sort sorting a list of random numbers.
Պատահական թվերի ցուցակի տեսակավորման օրինակ կենտ-զույգ եղանակով.


Դասը Տեսակավորման ալգորիթմ
Տվյալների կառուցվածքը Զանգված
Վատագույն արդյունք O(n^2)

Կենտ-զույգ տեսակավորումը համեմատաբար պարզ տեսակավորման ալգորիթմ է։ Այն գործում է` համեմատելով ցուցակի բոլոր (կենտ, զույգ) իրար հաջորդող էլեմենտների համարակալված զույգերը, և եթե որևէ զույգը սխալ հերթականությամբ է (առաջինը երկրորդից մեծ է), էլեմենտները տեղերով փոխվում են։ Հաջորդ քայլը կրկնում է նույն գործընթացը հաջորդական տարրերի համարակալված զույգերի համար։ Այնուհետև այն ընտրում է (զույգ, կենտ) և (կենտ, զույգ) քայլերի միջև մինչև ցուցակը կտեսակավորվի։ Այս գործընթացը կարելի է նմանեցնել պղպջակային տեսակավորում կիրառող զուգահեռ պրոցեսորներ օգտագործելուն, որոնցից յուրաքանչյուրը սկսում է գործել ցուցակի տարբեր կետերից (բոլոր կենտերը սկսում են առաջին քայլը)։

Կենտ-զույգ տեսակավորումը համեմատական տեսակավորում է, որը հիմնված է պղպջակային տեսակավորման վրա, որի հետ ունի բազմաթիվ ընդհանուր բնութագրեր։ Տեսակավորման այս ալգորիթմը միայն քանակապես է ավելի դժվար կիրառել, քան պղպջակային տեսակավորումը։

[1]

Ալգորիթմ[խմբագրել]

Ենթադրվում է զրոյական ինդեքս։

/* Ենթադրվում է, որ a-ն արժեքների զանգված է: */
var sorted = false;
while(!sorted)
{
    sorted=true;
    for(var i = 1; i < list.length-1; i += 2)
    {
        if(a[i] > a[i+1])
        {
            swap(a, i, i+1);
            sorted = false;
        }
    }
 
    for(var i = 0; i < list.length-1; i += 2)
    {
        if(a[i] > a[i+1])
        {
            swap(a, i, i+1);
            sorted = false;
        }
    }
}

Հղումներ[խմբագրել]

Կաղապար:Compu-sci-stub