«Ներդրմամբ տեսակավորում»–ի խմբագրումների տարբերություն
չ oգտվելով ԱՎԲ |
չ փոխարինվեց: ` → ՝ (4) oգտվելով ԱՎԲ |
||
Տող 6. | Տող 6. | ||
* Այն կարող է տեսակավորել շարքը, դրա տեսակավորման ընթացքում ; |
* Այն կարող է տեսակավորել շարքը, դրա տեսակավորման ընթացքում ; |
||
* Այն չի պահանջում ժամանակավոր հիշողության տիրույթ նույնիսկ ստեկում։ |
* Այն չի պահանջում ժամանակավոր հիշողության տիրույթ նույնիսկ ստեկում։ |
||
Ալգորիթմի բարձր |
Ալգորիթմի բարձր բարդությունը՝ [[O]](''n''²). համարվում է նրա բացասական կողմը։ |
||
[[Պատկեր:Insertion-sort-example-300px.gif|300px|thumb|right|Ներդրմամբ տեսակավորման օրինակ.Որը, ստուգում է յուրաքանչյուր տարր և այն դնում ճիշտ կարգավորված ցուցակում։]] |
[[Պատկեր:Insertion-sort-example-300px.gif|300px|thumb|right|Ներդրմամբ տեսակավորման օրինակ.Որը, ստուգում է յուրաքանչյուր տարր և այն դնում ճիշտ կարգավորված ցուցակում։]] |
||
Տող 12. | Տող 12. | ||
== Նկարագրություն == |
== Նկարագրություն == |
||
Ալգորիթմի յուրաքանչյուր քայլում մենք ընտրում ենք մուտքագրված տվյալներից մեկ էլեմենտ և տեղադրում ենք այն համապատասխան տեղը, որտեղ արդեն տեսակավորված են, այնքան ժամանակ քանի դեռ մուտքագրված տվյալների հավաքածուները ավարտված կլինեն։ Ելքային զանգվածից հերթական էլեմենտի ընտրման մեթոդը կատարված է, այն կարող է օգտագործվել ցանկացած ընտրման ալգորիթմում, սովորաբար(կայուն տեսակավորման ալգորիթմի ստացման գնով), էլեմենտները մուտքային զանգվածում դրվում են իրենց հայտնվելու հաջորդականությամբ։ Ներքևում գրվածա ալգորիթմը օգտագործում է հենց այս стратегинa:Ի տարբերություն պղպջակային և ընտրման տեսակավորումների, ներդրմամբ տեսակավորման համեմատության որակը կախված է տողի նախնական հաջորդականությունից, եթե տողը արդեն տեսակավորված է համեմատությունների քայլերի քանակը հավասար է n-1, հակառակ |
Ալգորիթմի յուրաքանչյուր քայլում մենք ընտրում ենք մուտքագրված տվյալներից մեկ էլեմենտ և տեղադրում ենք այն համապատասխան տեղը, որտեղ արդեն տեսակավորված են, այնքան ժամանակ քանի դեռ մուտքագրված տվյալների հավաքածուները ավարտված կլինեն։ Ելքային զանգվածից հերթական էլեմենտի ընտրման մեթոդը կատարված է, այն կարող է օգտագործվել ցանկացած ընտրման ալգորիթմում, սովորաբար(կայուն տեսակավորման ալգորիթմի ստացման գնով), էլեմենտները մուտքային զանգվածում դրվում են իրենց հայտնվելու հաջորդականությամբ։ Ներքևում գրվածա ալգորիթմը օգտագործում է հենց այս стратегинa:Ի տարբերություն պղպջակային և ընտրման տեսակավորումների, ներդրմամբ տեսակավորման համեմատության որակը կախված է տողի նախնական հաջորդականությունից, եթե տողը արդեն տեսակավորված է համեմատությունների քայլերի քանակը հավասար է n-1, հակառակ դեպքում՝ նրա քայլերի քանակը հավասար է հաջորդականության մեծության n² աստիճանի։ |
||
[[Պատկեր:Insertion sort animation.gif|thumb|right|280px|Գրաֆիկական օրինակ. Հորիզոնական առանցքը ներակայացնում է զանգվածը, իսկ ուղղահայաց առանցքը այդ զանգվածի դասավորվածությունը]] |
[[Պատկեր:Insertion sort animation.gif|thumb|right|280px|Գրաֆիկական օրինակ. Հորիզոնական առանցքը ներակայացնում է զանգվածը, իսկ ուղղահայաց առանցքը այդ զանգվածի դասավորվածությունը]] |
||
Տող 18. | Տող 18. | ||
== Ալգորիթմի վերլուծություն == |
== Ալգորիթմի վերլուծություն == |
||
Ալգորիթմի կատարման ժամանակը կախված է մուտքային տվյալներից.ինչքան շատ բազմություն է պետք տեսակավորել, այնքան շատ ժամանակ է օգտագործվում։ Հենց այդքան ժամանակ էլ օգտագործում է զանգվածի ելքային տեսակավորումը։ Այսպիսով, լավագույն դեպքում զանգվածը համարվում է տեսակավորված, իսկ վատագույն |
Ալգորիթմի կատարման ժամանակը կախված է մուտքային տվյալներից.ինչքան շատ բազմություն է պետք տեսակավորել, այնքան շատ ժամանակ է օգտագործվում։ Հենց այդքան ժամանակ էլ օգտագործում է զանգվածի ելքային տեսակավորումը։ Այսպիսով, լավագույն դեպքում զանգվածը համարվում է տեսակավորված, իսկ վատագույն դեպքը՝հակառակ կարգով տեսակավորված զանգվածը։ Ժամանակավոր [[Сложность алгоритма|ալգորիթմի դժվարությունը]] ելքային տվյալների վատագույն տարբերակի դեպքում — θ(n²)է. |
||
Օրինակ։ Այս աղյուսակը ցույց է տալիս տեսակավորման քայլերի հաջորդականությունը։{5, 7, 0, 3, 4, 2, 6, 1}. Ընդհանուր առմամբ այն բաղկացած է 17 քայլերից։ |
Օրինակ։ Այս աղյուսակը ցույց է տալիս տեսակավորման քայլերի հաջորդականությունը։{5, 7, 0, 3, 4, 2, 6, 1}. Ընդհանուր առմամբ այն բաղկացած է 17 քայլերից։ |
||
Տող 39. | Տող 39. | ||
== Ալգորիթմների բնութագրման լեզու== |
== Ալգորիթմների բնութագրման լեզու== |
||
'''Մուտք''': A զանգվածը կազմված է հետևյալ |
'''Մուտք''': A զանգվածը կազմված է հետևյալ էլեմենտներից՝A[1], A[2], ..., A[n] |
||
'''for''' i = 2, 3, ..., n: <!-- начинаем с i=2, это не ошибка. Можно и с i=1, но это просто будет лишняя итерация --> |
'''for''' i = 2, 3, ..., n: <!-- начинаем с i=2, это не ошибка. Можно и с i=1, но это просто будет лишняя итерация --> |
18:21, 22 Հուլիսի 2016-ի տարբերակ
Ներդրմամբ տեսակավորումը — պարզ տեսակավորման ալգորիթմ է։ Չնայած այս տեսակավորման ալգորիթմը իր էֆեկտիվությամբ առավել բարդ է(ինչպես արագ տեսակավորումը), այն ունի իր առավելությունները։
- Էֆեկտիվ է տվյալների ոչ մեծ հավաքածուններում, կարող է լինել որակյալ տասնյակ տարրերից կազմված տվյալների հավաքածուններում;
- Էֆեկտիվ է այն հավաքածուններում, որոնք արդեն մասամբ տեսակավորված են;
- Այս ալգորիթմը հարմար տեսակավորման ալգորիթմ է(չի փոխում արդեն տեսակավորված էլեմենտների հաջորդականությունը);
- Այն կարող է տեսակավորել շարքը, դրա տեսակավորման ընթացքում ;
- Այն չի պահանջում ժամանակավոր հիշողության տիրույթ նույնիսկ ստեկում։
Ալգորիթմի բարձր բարդությունը՝ 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 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--;
}
}
}