Ներդրմամբ տեսակավորում

**Ներդրմամբ տեսակավորումը** պարզ տեսակավորման ալգորիթմ է, որը ստեղծում է վերջնական սորտավորված զանգված կամ ցանկ։ Այն այդքան էֆեկտիվ չէ մեծ ցանկերի համար, տվյալ ալգորիթմը ավելի դանդաղ է աշխատում քան արագ տեսակավորումը, կույտային տեսակավորումը կամ միաձուլման տեսակավորումը։ Այնուամենայնիվ մուտքային սորտավորումը ունի իր առավելությունները, որոնցից են՝

* Պարզ ռեալիզացումը, Ջոն Բենթլին՝ համակարգչային գիտնակնը, ներկայացնում է երեք տողով C լեզվով
* Էֆեկտիվ փոքր տվյալների սահմաններում
* Գործնականում ավելի էֆեկտիվ է քան ուրիշ քառակուսային ալգորիթմեր (Օ(*n*2))՝ ընտրանքային տեսակավորում կամ պղպջակային տեսակավորում
* Այն կարող է տեսակավորել շարքը, դրա տեսակավորման ընթացքում
* Այն չի պահանջում ժամանակավոր հիշողության տիրույթ նույնիսկ ստեկում

300px|thumb|right|Ներդրմամբ տեսակավորման օրինակ.Որը, ստուգում է յուրաքանչյուր տարր և այն դնում ճիշտ կարգավորված ցուցակում։

## Նկարագրություն
Ալգորիթմի յուրաքանչյուր քայլում մենք ընտրում ենք մուտքագրված տվյալներից մեկ էլեմենտ և տեղադրում ենք այն համապատասխան տեղը, որտեղ արդեն տեսակավորված են, այնքան ժամանակ քանի դեռ մուտքագրված տվյալների հավաքածուները ավարտված կլինեն։ Ելքային զանգվածից հերթական էլեմենտի ընտրման մեթոդը կատարված է, այն կարող է օգտագործվել ցանկացած ընտրման ալգորիթմում, սովորաբար(կայուն տեսակավորման ալգորիթմի ստացման գնով), էլեմենտները մուտքային զանգվածում դրվում են իրենց հայտնվելու հաջորդականությամբ։ Ներքևում գրվածա ալգորիթմը օգտագործում է հենց այս стратегинa:Ի տարբերություն պղպջակային և ընտրման տեսակավորումների, ներդրմամբ տեսակավորման համեմատության որակը կախված է տողի նախնական հաջորդականությունից, եթե տողը արդեն տեսակավորված է համեմատությունների քայլերի քանակը հավասար է n-1, հակառակ դեպքում՝ նրա քայլերի քանակը հավասար է հաջորդականության մեծության n² աստիճանի։

## Ալգորիթմի վերլուծություն
Ալգորիթմի կատարման ժամանակը կախված է մուտքային տվյալներից.ինչքան շատ բազմություն է պետք տեսակավորել, այնքան շատ ժամանակ է օգտագործվում։ Հենց այդքան ժամանակ էլ օգտագործում է զանգվածի ելքային տեսակավորումը։ Այսպիսով, լավագույն դեպքում զանգվածը համարվում է տեսակավորված, իսկ վատագույն դեպքը՝հակառակ կարգով տեսակավորված զանգվածը։ Ժամանակավոր ալգորիթմի դժվարությունը ելքային տվյալների վատագույն տարբերակի դեպքում — θ(n²)է.
Օրինակ։ Այս աղյուսակը ցույց է տալիս տեսակավորման քայլերի հաջորդականությունը։{5, 7, 0, 3, 4, 2, 6, 1}. Ընդհանուր առմամբ այն բաղկացած է 17 քայլերից։

5	7	0	3	4	2	6	1	 	 (0)

5	7	0	3	4	2	6	1	 	 (0)

**0**	5	7	3	4	2	6	1	 	 (2)

0	**3**	5	7	4	2	willi6	1	 	 (2)

0	3	**4**	5	7	2	6	1	 	 (2)

0	**2**	3	4	5	7	6	1	 	 (4)

0	2	3	4	5	**6**	7	1	 	 (1)

0	**1**	2	3	4	5	6	7	 	 (6)

## Ալգորիթմների բնութագրման լեզու
**Մուտք**։ A զանգվածը կազմված է հետևյալ էլեմենտներից՝A[1], A[2], ..., A[n]
 
 **for** i = 2, 3, ..., n:  
     key := A[i]
     j := i - 1
     **while** j > 0 **and** A[j] > key:
         A[j + 1] := A[j]
         j := j - 1
     A[j + 1] := key

## Իրականացումը C++

```cpp
void insertionSort(int arr[], int length)
{
      int i, j, tmp;
      for (i = 1; i < length; ++i)
      {
            j = i;
            while (j > 0 && arr[j - 1] > arr[j])
            {
                  tmp = arr[j];
                  arr[j] = arr[j - 1];
                  arr[j - 1] = tmp;
                  j--;
            }
      }
}
```


## Ծանոթագրություններ

* Անիմացված ալգորիթմերի պատկերացումը

Կատեգորիա:Տեսակավորման ալգորիթմ