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

Կենտ-զույգ տեսակավորում
Տեսակ	տեսակավորման ալգորիթմ
Տվյալների կառուցվածք	$O(1)$
Վատագույն դեպքում կատարումը	$O(n^{2})$
Լավագույն դեպքում կատարումը	$O(n)$
Օգտագործում է	զանգված
Հայտնաբերող	Nico Habermann?

Կենտ-զույգ տեսակավորումը համեմատաբար պարզ տեսակավորման ալգորիթմ է։

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

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

Ալգորիթմ

Ալգորիթմի օրինակը C++ լեզվով։

 template <class T>
void OddEvenSort (T a[], int n)
{
    for (int i = 0 ; i < n ; i++)
    {
         if (i & 1) // 'i' is odd
         {
             for (int j = 2 ; j < n ; j += 2)
             {     
                  if (a[j] < a[j-1])
                      swap (a[j-1], a[j]) ;
             }
          }
          else
          {  
              for (int j = 1 ; j < n ; j += 2)
              {
                   if (a[j] < a[j-1])
                       swap (a[j-1], a[j]) ;
              } 
          }
    }
}

Ալգորիթմի օրինակը javascript լեզվով։

/* Ենթադրվում է, որ 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;
        }
    }
}