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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Կոկտեյլային տեսակավորում
Sorting shaker sort anim.gif
Տեսակ տեսակավորման ալգորիթմ
Տվյալների կառուցվածք O(1)
Վատագույն դեպքում կատարումը O(n^2)
Լավագույն դեպքում կատարումը O(n)
Օգտագործում է զանգված


Կոկտեյլային տեսակավորումը հայտնի է որպես երկկողմանի պղպջակների տեսակավորում, կոկտեյլային շեյկեի տեսակավորում, շեյկեր տեսակավորում (որը կարող է նաև հանդիսանալ ընտրության տեսակավորման տարբերակ) 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)։

Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]