Կոկտեյլային տեսակավորում

Կոկտեյլային տեսակավորումը հայտնի է որպես երկկողմանի պղպջակների տեսակավորում, կոկտեյլային շեյկեի տեսակավորում, շեյկեր տեսակավորում (որը կարող է նաև հանդիսանալ ընտրության տեսակավորման տարբերակ) ripple sort, shuffle sort, shuttle sort կամ happy hour sort, որոնք պղպջակային տեսակավորման դասին են պատկանում և երկուսն էլ հանդիսանում են կայուն և համեմատության տեսակավորման ալգորիթմներ։ Ալգորիթմը տարբերվում է պղպջակային տեսակավորումից նրանով որ երկու ուղղություններով, որոնցից յուրաքանչյուրը անցնում ցուցակը։ Այս տեսակավորման ալգորիթմը տեսականորեն ավելի դժվար է իրականացնել, քան պղպջակային տեսակավորումը և լուծում է պղպջակային տեսակավորման այսպես կոչված կրիաային խնդիրը։

 Ալգորիթմ 
Կոկտեյլային տեսակավորման ամենապարզ ձևը անցնում է ամբողջ ցուցակով ամեն անգամ։ 
 procedure cocktailSort( A ։ list of sortable items ) defined as։
 do
 swapped ։= false
 for each i in 0 to length( A ) - 2 do։
 if A[ i ] > A[ i + 1 ]  // ստուգենք թե արդյոք երկու էլեմենտներնէլ սխալ կարգով են թե ոչ
 swap( A[ i ], A[ i + 1 ] )  // երկու էլեմենտներն փոխվում են իրենց տեղերով
 swapped ։= true
 end if
 end for
 if swapped = false then
 // մենք կարող ենք ավարտել արտաքին loop-ը այստեղ եթե ոչ մի փոխանակում չկա
 break do-while loop
 end if
 swapped ։= false
 for each i in length( A ) - 2 to 0 do։
 if A[ i ] > A[ i + 1 ] then
 swap( A[ i ], A[ i + 1 ] )
 swapped ։= true
 end if
 end for
 while swapped // եթե ոչ մի էլեմենտներ փոխանակված չեն, ապա ցուցակը տեսակավորված է
 end procedure

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

 procedure cocktailSort( A ։ list of sortable items ) defined as։
 // `begin` և `end` նշում են առաջին և վերջին ինդեքսները, որոնք պետք է ստուգվեն 
 begin ։= -1
 end ։= length( A ) - 2
 do
 swapped ։= false
 // աճում է `begin` քանի որ `begin`-ին նախորդող տարրը ճիշտ տղում է
 begin ։= begin + 1
 for each i in begin to end do։
 if A[ i ] > A[ i + 1 ] then
 swap( A[ i ], A[ i + 1 ] )
 swapped ։= true
 end if
 end for
 if swapped = false then
 break do-while loop
 end if
 swapped ։= false
 // նվազում է `end` քանի որ `end`-ին նախորդող տարրը ճիշտ տեղում է
 end ։= end - 1
 for each i in end to begin do։
 if A[ i ] > A[ i + 1 ] then
 swap( A[ i ], A[ i + 1 ] )
 swapped ։= true
 end if
 end for
 while swapped
 end procedure

 Տարբերությունները պղպջակային տեսակավորումից 
Կոկտեյլային տեսակավորումը մի փոքր շեղված է պղպջակային տեսակավորումից։ Այն տարբերվում է, որ փոխարեն պարբերաբար ցուցակում վերևից ներքև տեղափոխվելու, այն անցնում է այլ կերպ ներքևից դեպի վերև, և ապա, վերևից ներքև։ Այն կարող է իրականացվել մի փոքր ավելի լավ, քան ստանդարտ պղպջակային տեսակավորումը։ Պատճառը այն է, որ պղպջակաին տեսակավորման ժամանակ միայն ցանկը միայն մեկ ուղղությամբ է տեղափոխվում և հետևաբար, կարող է միայն տեղափոխվել այն տարրերը, որոնք մեկ քայլ հետ կտեղափոխվեն յուրաքանչյուր պարբերաշրջանի ժամանակ։

Օրինակ մի ցանկ, որը պարունակում է հետևյալ տարրերը (2, 3, 4, 5, 1), որը անհրաժեշտ է տեղափոխվի մեկ անգամ կոկտեյլային տեսակավորման միջոցով, տեսակավորված լինելու համար, բայց եթե օգտագործենք աճման պղպջակային տեսակավորումը ապա պետք է կատարվի չորս անցնում։ Մեկ կոկտեյլային տեսակավորման անցումը պետք է հաշվարկվի որպես երկու պղպջակային տեսակավորման անցնում։ Որպես կանոն, կոկտեյլային տեսակավորումը երկու անգամ ավելի դանդաղ է քան պղպջակային տեսակավորումը։ Այլ օպտիմալ լուծում կլինի, որ կարող է լինել, որ ալգորիթմը հիշի, թե որտեղ է կատարվել վերջին փաստացի փոխանակումը։ Հաջորդ ցիկլի ժամանակ այնտեղ չեն լինի փոխանակումներ. այս սահմանափակումից զատ և ալգորիթմը ունի ավելի կարճ անցնումներ։ Քանի որ կոկտեյլային տեսակավորման անցումները bidirectionally, հնարավոր փոխանակումների տիրույթը պետք է փորձարկվի, ինչը կնվազեցնի անցումները, դրանով իսկ նվազեցնելով ընդհանուր ժամանակ։

 Բարդություն 
Կոկտեյլային տեսակավորման բարդությունը big O notation  է համար, թե վատագույն և միջին դեպքում, սակայն այն դառնում է ավելի մոտեթե ցուցակը հիմնականում պատվիրված առաջ կիրառելով տեսակավորումը ալգորիթմ, օրինակ, եթե յուրաքանչյուր տարրը գտնվում է դիրքորոշումը, որ տարբերվում է առավե k (k ≥ 1) դիրքերից, որ պատրաստվում է ավարտվում է, բարդությունը կոկտեյլ տեսակավորելու դառնում .

Կոկտեյլ տեսակավորել է նաև հակիրճ քննարկվում գրքում արվեստը համակարգչային ծրագրավորման հետ մեկտեղ, նման refinements է պղպջակների sort. Եզրափակելով, Knuth պետությունների մասին պղպջակների տեսակավորման և դրա բարելավումներ (Knuth 1998, էջ 110)։

 Արտաքին հղումներ 
 Java source code and an animated demo of cocktail sort (called bi-directional bubble sort) and several other algorithms 
 .NET Implementation of cocktail sort and several other algorithms 
 Interactive demo of cocktail sort