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

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

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

Ալգորիթմ

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

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}\leq 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 ∈ Θ(n²) համեմատությունների համար։ Յուրաքանչյուր այս ստուգում պահանջում է մեկ փոխանակման n − 1 տարրերի համար (վերջին տարրը արդեն տեղում է)։

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

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

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

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

Տարբերակներ

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