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

Վիքիպեդիայից՝ ազատ հանրագիտարանից

Դասը Տեսակավորման ալգորիթմ

Visualisation of shaker sort

տվյալների զանգված

ժամանակ О(n²)

լավագույն ժամանակ O(n)

միջին ժամանակ О(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, հնարավոր փոխանակումների տիրույթը պետք է փորձարկվի, ինչը կնվազեցնի անցումները, դրանով իսկ նվազեցնելով ընդհանուր ժամանակ։

Another optimization can be that the algorithm remembers where the last actual swap has been done. In the next iteration, there will be no swaps beyond this limit and the algorithm has shorter passes. As the Cocktail sort goes bidirectionally, the range of possible swaps, which is the range to be tested, will reduce per pass, thus reducing the overall running time.

Բարդություն[խմբագրել]

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

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

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

Վիքիդարանի պատկերանիշը
Անգլերեն Վիքիդարանում կան նյութեր այս թեմայով՝
Sorting/Cocktail sort