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

**Կոկտեյլային տեսակավորումը** հայտնի է որպես երկկողմանի պղպջակների տեսակավորում, կոկտեյլային շեյկեի տեսակավորում, շեյկեր տեսակավորում (որը կարող է նաև հանդիսանալ ընտրության տեսակավորման տարբերակ) 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 O(n^2) է համար, թե վատագույն և միջին դեպքում, սակայն այն դառնում է ավելի մոտO(n)եթե ցուցակը հիմնականում պատվիրված առաջ կիրառելով տեսակավորումը ալգորիթմ, օրինակ, եթե յուրաքանչյուր տարրը գտնվում է դիրքորոշումը, որ տարբերվում է առավե k (k ≥ 1) դիրքերից, որ պատրաստվում է ավարտվում է, բարդությունը կոկտեյլ տեսակավորելու դառնում O(k*n).

Կոկտեյլ տեսակավորել է նաև հակիրճ քննարկվում գրքում արվեստը համակարգչային ծրագրավորման հետ մեկտեղ, նման 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