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

Ներդրմամբ տեսակավորումը — պարզ տեսակավորման ալգորիթմ է: Չնայած այս տեսակավորման ալգորիթմը իր էֆեկտիվությամբ առավել բարդ է(ինչպես արագ տեսակավորումը), այն ունի իր առավելությունները:

• Էֆեկտիվ է տվյալների ոչ մեծ հավաքածուններում,կարող է լինել որակյալ տասնյակ տարրերից կազմված տվյալների հավաքածուններում;
• Էֆեկտիվ է այն հավաքածուններում,որոնք արդեն մասամբ տեսակավորված են;
• Սա հարմարավետ տեսակավորման ալգորիթմ է(չի փոխում արդեն տեսակավորված էլեմենտների հաջորդականությունը);
• Կարող է տեսակավորել շարքը,դրա տեսակավորման ընթացքում ;
• Չի պահանջում ժամանակավոր հիշողության տիրույթ նույնիսկ ստեկում:

Ալգորիթմի բարձր բարդությունը` O(n²). համարվում է նրա բացասական կողմը:

Ներդրմամբ տեսակավորման օրինակ.Որը,ստուգում է յուրաքանչյուր տարր դնում է այն ճիշտ կարգավորված ցուցակում:

Նկարագրություն

Ալգորիթմի յուրաքանչյուր քայլում մենք ընտրում ենք մուտքագրված տվյալներից մեկ էլեմենտ և տեղադրում ենք այն համապատասխան տեղը,որտեղ արդեն տեսակավորված են,այնքան ժամանակ քանի դեռ մուտքագրված տվյալների հավաքածուները ավարտված կլինեն:Ելքային է զանգվածքից հերթական էլեմենտի ընտրման մեթոդը կատարված է,կարող է օգտագործվել ցանկացած ընտրման ալգորիթմ,սովորաբար(կայուն տեսակավորման ալգորիթմի ստացման գնով),էլեմենտները մուտքային զանգվածում դրվում են իրենց հայտնվելու հաջորդականությամբ:Ներքևում գրվածա ալգորիթմը օգտագործում է հենց այս стратегин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 6 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++

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--;
            }
      }
}

Հղում

• Анимированное представление алгоритма сортировки вставками