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

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

Կոկտեյլային տեսակավորումը հայտնի է որպես երկկողմանի պղպջակների տեսակավորում, կոկտեյլային շեյկեի տեսակավորում, շեյկեր տեսակավորում (որը կարող է նաև հանդիսանալ ընտրության տեսակավորման տարբերակ) 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 Արխիվացված 2006-10-08 Wayback Machine
• .NET Implementation of cocktail sort and several other algorithms Արխիվացված 2012-02-12 Wayback Machine
• Interactive demo of cocktail sort