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

դաս տեսակավորման ալգորիթմ

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

ժամանակ О(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):

Արտաքին հղումներ

• 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