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

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

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

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

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

Միջին ժամանակ О(n²)

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

Selection Sort Animation

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

Ալգորիթմ

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

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) փոխանակումը ընդդեմ Ο(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 տեսակավորումը կարող է ավելի արագ լինել: