Ընտրության տեսակավորում

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

Ընտրության տեսակավորում

Selection Sort Animation

Տվյալներ զանգված

Ժամանակ О(n2)

Լավագույն ժամանակ О(n2)

Միջին ժամանակ О(n2)

Տարածություն О(n) ընդհանուր , O(1) օժանդակ

Selection Sort Animation

Ընտրության տեսակավորումը տեսակավորուման ալգորիթմ է, մասնավորապես տվյալների համեմատության տեսակավորում է։ Այն ունի O(n2) բարդությունը, դարձնելով անարդյունավետ խոշոր ցուցակները, և ընդհանրապես այն որպես ալգորիթմ իրականացվում է ավելի վատ, քան համանման ներդրման տեսակավորումը։ Ընտրությանը տեսակավոումը նշանակալի է իր պարզությամբ և ալգորիթմի առավելությունը կայանում է նրանում, որ կարող է կատարել առավել բարդ խնդիրներ, մասնավորապես երբ օժանդակ հիշողությունը սահմանափակ է։

Ալգորիթմ[խմբագրել]

Ալգորիթմը աշխատում է հետևյալ կերպ `

  1. Գտնել նվազագույն արժեքը ցուցակում,
  2. Փոխանակել այն արժեքի հետ, որը գտնվում է առաջին տեղում,
  3. Վերը նշված քայլերը կրկնել համար ցուցակի մնացած մասի համար (սկսած երկրորդ հորիզոնականը զբաղեցնողից մինչև հաջորդը և այդպես յուրաքանչյուր անգամ):

Ցուցակի արդյունավետ կերպով բաժանվում է երկու մասի. ենթացուցակ, որն արդեն տեսակավորված է, կառուցված ձախից աջ, և գտնվում է սկզբում, և ենթացուցակ, որը պետք է տեսակավորվի, զբաղեցնելով համախմբում մնացած մասը:

Ահա մի օրինակ տեսակավորման ալգորիթմից հինգ տարրերի տեսակավորման համար:

64 25 12 22 11

11 25 12 22 64

11 12 25 22 64

11 12 22 25 64

11 12 22 25 64

(Ոչինչ փոփոխված չի հայտնվի այս վերջին տողում, քանի որ վերջին 2 թվերն արդեն, տեսակավորված էին)

Ընտրությունը տեսակավումը նույնպես կարող է օգտագործվել ցուցակային ստրուկտուրաներում, որ կարող է ավելացնել և հեռացնել արդյունավետ կերպով, օրինակ, հղումների ցուցակը: Այս դեպքում ավելի տարածված է հանել նվազագույն տարրը մնացած ցանկից, և ապա տեղադրեք այն տեսակավորված արժեքների վերջում Օրինակ `

64 25 12 22 11

11 64 25 12 22

11 12 64 25 22

11 12 22 64 25

11 12 22 25 64
/ * A [0]-ից  [n-1] է զանգված է տեսակավորեու համար * /
int iPos;
int iMin;
/ * Նախնական դիրքը ամբողջ զանգվածում* /
/ * (Կարող է անել iPos <n-1, քանի որ միայնակ տարր է նաև նվազագույն տարրը) * /
for (iPos = 0; iPos < n; iPos++)
{
    / * Գտնել նվազագույն տարրը չտեսակավորված [iPos ..  n-1]ում * /
    / * Վերագրել նվազագույն առաջին տարրը * /
  iMin = iPos;
 / * Ստուգել մյուս բոլոր տարրերի * /
  for (i = iPos+1; i < n; i++)
    {
          / * Եթե այս տարր ավելի փոքր է, ապա դա նոր նվազագույնն է * /  
      if (a[i] < a[iMin])
        {
        / * Գտել նոր նվազագույնը, հիշել է իր ինդեքսը * /
          iMin = i;
        }
    }
 
  / * IMin նվազագույն տարրի  ինդեքսն է. Այն փոխանակային ընթացիկ դիրքում է * /
  if ( iMin != iPos )
  {
    swap(a, iPos, iMin);
  }
}

Mathematical definition[խմբագրել]

Թող L լինի ոչ դատարկset և f : L \to L f(L) = L' where։

  1. L' is a permutation of L,
  2. e_i \le e_{i+1} for all e \in L' and i \in \mathbb{N},
  3. f(L) =
\begin{cases}
L, & \mbox{if }|L| = 1\\
\{s\} \cup f(L_{s}), & \mbox{otherwise}
\end{cases},
  4. s նվազագույն L, and
  5. L_s is the set of elements of L without one instance of the smallest element of L.

Վերլուծություն[խմբագրել]

Ընտրության տեսակավորումը դժվար չէ վերլուծել համեմատ այլ տեսակավորման ալգորիթմների, քանի որ հանգույցներից ոչ մեկը չի ազդում տվյալները զանվածի վրա։ Ընտրելիս, իսկ ամենափոքր տարրը պահանջում ստուգել բոլոր n տարրեր (այս ունենում n - 1 համեմատություններ) և այնուհետև փոխանակում առաջին տեղում։ Գտնելով հաջորդ ամենափոքր տարրը պահանջվում ստուգել մնացածn − 1 տարրերը և այսպես շարունակ , for (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n2) համեմատությունների համար։ Յուրաքանչյուր այս ստուգում պահանջում է մեկ փոխանակման n − 1 տարրերի համար (վերջին տարրը արդեն տեղում է)։

Համեմատած այլ տեսակավորման ալգորիթմների[խմբագրել]

Պարզ միջինի դեպքում Θ(n2) ընտրությանը տեսակավորման ալգորիթմերը գրեթե միշտ իրենցից ներկայացնում են պղպջակային տեսակավորում և գաճաճային տեսակավորում, բայց ընդհանուր առմամբ ներկայացվում է ներդրման տեսակավորման կողմից։ Ներդրման տեսակավորումը շատ նման է, որ հետո k կրկնությունից հետո, զանգվածի մեջ առաջին k տարրերը տեսակավորված են ըստ հերթականության։ Ներդրման տեսակավորման առավելությունը այն է, որ միայն ստուգում է այնքան տարրեր, որքան անհրաժեշտ է ըստ հերթականությամբ մինչև k + 1րդ տարր, իսկ ընտրության տեսակավումը պետք է ստուգի մյուս մնացած տարրերը մինչև կգտնի k + 1-րդ տարրը։

Պարզ հաշվարկը ցույց է տալիս, որ ներդրման տեսակավորումը որպես կանոն, իրականացվում է, կիսով չափ ավելի քիչ համեմատություններով, քան ընտրության տեսակավորման, թեև դա կարող է իրականացնել ճիշտ այնպես, ինչպես շատ կամ ավելի քիչ կախված, որպեսզի զանգված էր առաջ տեսակավորում։ Այն կարելի է դիտարկել իբրև առավելություն որոշ իրական ժամանակում դիմումների համար, որ ընտրության տեսակավորումը կկատարի ինքնաբերաբար անկախ զանգվածի կարգից, իսկ ներդրման տեսակավորման ժամանակ կարող է զգալիորեն տարբերվել։ Սակայն սա ավելի հաճախ որպես առավելություն է դիտարկվում ներդրման տեսակավորման համար նրանով, որ այն իրականացվում է շատ ավելի արդյունավետ, եթե զանգվածը արդեն տեսակավորված է կամ «մոտ է տեսակավորման»։

Մինչ ընտրության տեսակավումը նախընտրելի է ներդրման տեսակավորումից թվեր գրելու առումով (Θ(n) փոխանակումը ընդդեմ Ο(n2) փոխանակման), այն գրեթե միշտ, շատ դեպքերում գերազանցում գրածների համարը , որ ցիկլի տեսակավորումը իրականացնում է, քանի որ ցիկլի տեսակավորումը տեսականորեն օպտիմալ է գրածների թվով։ Սա կարող է կարևոր լինել, եթե գրում են, զգալիորեն ավելի թանկ է, քան կարդում է, օրինակ, ինչպես EEPROM կամ Flash հիշողության մեջ, ուր ամեն մի գրած փոքրացվում է lifespan հիշողության մեջ։ Վերջապես, ընտրության տեսակավորում ներկայացնում է ավելի մեծ զանգվածներ Θ(n log n) բաժանենք-նվաճել ալգորիթմներ ինչպիսիք են mergesort։ Սակայն, ներդրման կամ ընտրության տեսակավորումները երկուսն էլ , սովորաբար, ավելի արագ են փոքր զանգվածների համար (այսինքն, ավելի քիչ, քան 10-20 տարրեր)։ Օգտակար օպտիմալացման համար գործնականում ռեկուրսիվ ալգորիթմներից պետքէ անցնել ներդրման կամ ընտրության տեսակավորման «բավարար փոքր» ենթացուցակների։

Տարբերակներ[խմբագրել]

Հանգույցային տեսակավորումը մեծապես կատարելագործում է հիմնական ալգորիթմը օգտագործելով հանգույցային տվյալների կառուցվածքը արդյունքում արագացնում ամենափոքր տվյալի հայտնաբերումը և հեռացումը։ Եթե իրականացվում է ճիշտ, հանգույցը թույլ կտա գտնել հաջորդ ամենացածր տարր Θ( n log n )։Θ(log n)-ի ժամանակի փոխարեն Θ(n) ներքին հանգույցի համար նորմալ ընտրության տեսակավորում, նվազեցնելով ընդհանուր ժամանակը Θ(n log n)։ Երկկողմանի տարբերակը ընտրության տեսակավորման, որը կոչվում է կոկտեյլային տեսակավորման, մի ալգորիթմ է, որը գտնում է, ինչպես նվազագույն այնպես էլ առավելագույն արժեքները ցանկում յուրաքանչյուր անցման ժամանակ։ Սա նվազեցնում է ստուգումների թիվը ցուցակը ըստ 2 վերացնող գործոնի մի հանգույցով միացնում իրար, սակայն դեռևս փաստացի նվազեցնել թիվը համեմատություններ կամ փոխանակումներ։ Նշենք կոկտեյլային տեսակավորումը ավելի հաճախ վերաբերում է պղպջակային տեսակավորմանը։ Ընտրության տեսակավորումը կարող են իրականացվել է որպես կայուն տեսակավորում։ Եթե փոխանակվում է քայլ 2-ը նվազագույն արժեքը տեղադրված է առաջին տեղում (այսինքն, բոլոր միջամտող տարրերը տեղափոխվում են ներքև), այսինքն ալգորիթմ կայուն է։ Սակայն այս փոփոխումը պահանջում է տվյալների կառույց, որ պաշտպանում է արդյունավետ տեղադրումները կամ ջնջումները, ինչպիսին է կցված ցանկը, որը հանգեցնում է Θ(n2) գրվածի ներկայացմանը։ Bingo տեսակավորման ժամանակ, տարրերն դասավորվածեն կրկնվող տեսքով, իսկ մնացած տվյալների համար անհրաժեշտ է գտնել ամենամեծ արժեքը, և տեղափոխել բոլոր տարրերի արժեքներն իրենց վերջնական գտնվելու վայրը։ Նման հաշվարկի տեսակավորմանը սա արդյունավետ տարբերակ է, եթե կան շատ կրկնօրինակ արժեքները։ Իսկապես, ընտրության տեսակավորումը անցկացնում է մնացած տվյալները յուրաքանչյուր տեղափոխված տվյալի համար։ Bingo տեսակավորումը իրականացնում է երկու անցում յուրաքանչյուր արժեքի համար. մեկը անցում է կատարում գտնելու համար հաջորդ ամենամեծ արժեքը, և մեկ անցում տեղափոխում է ցանկացած տվյալ այնտեղ, որտեղ իր վերջնական արժեքը պետք է գտնվի։ Այսպես, եթե միջին հաշվարկով կան ավելի քան երկու իրար համարժեք տարրեր, bingo տեսակավորումը կարող է ավելի արագլինել։