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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Ներդրմամբ տեսակավորում
Պատահական թվերի մուտքային տեսակավորուման օրինակը։
Տեսակ Տեսակավորման ալգորիթմ
Տվյալների կառուցվածք Զանգված
Վատագույն դեպքում կատարումը համեմատումը, փոխարինումը
Լավագույն դեպքում կատարումը համեմատումը, փոխարինումը
Միջինում կատարումը համեմատումը, փոխարինումը
Վատագույն դեպքում տարածքի բարդությունը ընդհանուր, լրացուցիչ
Insertion sort Վիքիպահեստում


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

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


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

Նկարագրություն[խմբագրել | խմբագրել կոդը]

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

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

Հղումներ[խմբագրել | խմբագրել կոդը]

  1. Bentley, Jon (2000). Programming Pearls. ACM Press/Addison–Wesley.