«Ներդրմամբ տեսակավորում»–ի խմբագրումների տարբերություն
No edit summary |
No edit summary |
||
Տող 9. | Տող 9. | ||
[[File:Insertion-sort-example-300px.gif|300px|thumb|right|Ներդրմամբ տեսակավորման օրինակ.Որը,ստուգում է յուրաքանչյուր տարր դնում է այն ճիշտ կարգավորված ցուցակում:]] |
[[File:Insertion-sort-example-300px.gif|300px|thumb|right|Ներդրմամբ տեսակավորման օրինակ.Որը,ստուգում է յուրաքանչյուր տարր դնում է այն ճիշտ կարգավորված ցուցակում:]] |
||
== Նկարագրություն == |
== Նկարագրություն == |
||
Ալգորիթմի յուրաքանչյուր քայլում մենք ընտրում ենք մուտքագրված տվյալներից մեկ էլեմենտ և տեղադրում ենք այն համապատասխան տեղը,որտեղ արդեն տեսակավորված են,այնքան ժամանակ քանի դեռ մուտքագրված տվյալների հավաքածուները ավարտված կլինեն:Ելքային է զանգվածքից հերթական էլեմենտի ընտրման մեթոդը կատարված է,կարող է օգտագործվել ցանկացած ընտրման ալգորիթմ,սովորաբար(կայուն տեսակավորման ալգորիթմի ստացման գնով),էլեմենտները մուտքային զանգվածում դրվում են իրենց հայտնվելու հաջորդականությամբ:Ներքևում գրվածա ալգորիթմը օգտագործում է հենց այս стратегин |
Ալգորիթմի յուրաքանչյուր քայլում մենք ընտրում ենք մուտքագրված տվյալներից մեկ էլեմենտ և տեղադրում ենք այն համապատասխան տեղը,որտեղ արդեն տեսակավորված են,այնքան ժամանակ քանի դեռ մուտքագրված տվյալների հավաքածուները ավարտված կլինեն:Ելքային է զանգվածքից հերթական էլեմենտի ընտրման մեթոդը կատարված է,կարող է օգտագործվել ցանկացած ընտրման ալգորիթմ,սովորաբար(կայուն տեսակավորման ալգորիթմի ստացման գնով),էլեմենտները մուտքային զանգվածում դրվում են իրենց հայտնվելու հաջորդականությամբ:Ներքևում գրվածա ալգորիթմը օգտագործում է հենց այս стратегин |
||
== Ալգորիթմի վերլուծություն == |
== Ալգորիթմի վերլուծություն == |
||
[[Image:Insertion sort animation.gif|thumb|right|280px|Գրաֆիկական օրինակ. Հորիզոնական առանցքը ներակայացնում է զանգվածը,իսկ ուղղահայաց առաբցքը այդ զանգվածի դասավորվածությունը]] |
[[Image:Insertion sort animation.gif|thumb|right|280px|Գրաֆիկական օրինակ. Հորիզոնական առանցքը ներակայացնում է զանգվածը,իսկ ուղղահայաց առաբցքը այդ զանգվածի դասավորվածությունը]] |
||
Ալգորիթմի կատարման ժամանակը կախված է մուտքային տվյալներից.ինչքան շատ բազմություն է պետք տեսակավորել ,այնքան շատ ժամանակ է օգտագործում տեսակավորումը:Հենց այդքան ժամանակա էլ օգտագործում է զանգվածի ելքյին դասակարգումը:Այսպիսով,լավագույն դեպքում զանգվածը համարվում է տեսակավորված,իսկ վատագույն դեպքում`հակառակ կարգով դասակարգված զանգվածը:Ժամանակավոր [[Сложность алгоритма|ալգորիթմի դժվարությունը]]ելքային տվյալների վատագույն տարբերակօ դեպքում — θ(n²). |
Ալգորիթմի կատարման ժամանակը կախված է մուտքային տվյալներից.ինչքան շատ բազմություն է պետք տեսակավորել ,այնքան շատ ժամանակ է օգտագործում տեսակավորումը:Հենց այդքան ժամանակա էլ օգտագործում է զանգվածի ելքյին դասակարգումը:Այսպիսով,լավագույն դեպքում զանգվածը համարվում է տեսակավորված,իսկ վատագույն դեպքում`հակառակ կարգով դասակարգված զանգվածը:Ժամանակավոր [[Сложность алгоритма|ալգորիթմի դժվարությունը]]ելքային տվյալների վատագույն տարբերակօ դեպքում — θ(n²). |
||
== Ալգորիթմների բնութագրման լեզու |
== Ալգորիթմների բնութագրման լեզու |
||
'''Մուտք''': A զանգվածը կազմված է հետևյալ էլեմենտներից`A[1], A[2], ..., A[n] |
'''Մուտք''': A զանգվածը կազմված է հետևյալ էլեմենտներից`A[1], A[2], ..., A[n] |
||
Տող 32. | Տող 37. | ||
A[j + 1] := key |
A[j + 1] := key |
||
⚫ | |||
⚫ | |||
<source lang="cpp"> |
<source lang="cpp"> |
20:27, 23 Մայիսի 2011-ի տարբերակ
Ներդրմամբ տեսակավորումը — պարզ տեսակավորման ալգորիթմ է: Չնայած այս տեսակավորման ալգորիթմը իր էֆեկտիվությամբ առավել բարդ է(ինչպես արագ տեսակավորումը), այն ունի իր առավելությունները:
- Էֆեկտիվ է տվյալների ոչ մեծ հավաքածուններում,կարող է լինել որակյալ տասնյակ տարրերից կազմված տվյալների հավաքածուններում;
- Էֆեկտիվ է այն հավաքածուններում,որոնք արդեն մասամբ տեսակավորված են;
- Սա հարմարավետ տեսակավորման ալգորիթմ է(չի փոխում արդեն տեսակավորված էլեմենտների հաջորդականությունը);
- Կարող է տեսակավորել շարքը,դրա տեսակավորման ընթացքում ;
- Չի պահանջում ժամանակավոր հիշողության տիրույթ նույնիսկ ստեկում:
Ալգորիթմի բարձր բարդությունը O(n²). համարվում է նրա բացասական կողմը:
Նկարագրություն
Ալգորիթմի յուրաքանչյուր քայլում մենք ընտրում ենք մուտքագրված տվյալներից մեկ էլեմենտ և տեղադրում ենք այն համապատասխան տեղը,որտեղ արդեն տեսակավորված են,այնքան ժամանակ քանի դեռ մուտքագրված տվյալների հավաքածուները ավարտված կլինեն:Ելքային է զանգվածքից հերթական էլեմենտի ընտրման մեթոդը կատարված է,կարող է օգտագործվել ցանկացած ընտրման ալգորիթմ,սովորաբար(կայուն տեսակավորման ալգորիթմի ստացման գնով),էլեմենտները մուտքային զանգվածում դրվում են իրենց հայտնվելու հաջորդականությամբ:Ներքևում գրվածա ալգորիթմը օգտագործում է հենց այս стратегин
Ալգորիթմի վերլուծություն
Ալգորիթմի կատարման ժամանակը կախված է մուտքային տվյալներից.ինչքան շատ բազմություն է պետք տեսակավորել ,այնքան շատ ժամանակ է օգտագործում տեսակավորումը:Հենց այդքան ժամանակա էլ օգտագործում է զանգվածի ելքյին դասակարգումը:Այսպիսով,լավագույն դեպքում զանգվածը համարվում է տեսակավորված,իսկ վատագույն դեպքում`հակառակ կարգով դասակարգված զանգվածը:Ժամանակավոր ալգորիթմի դժվարությունըելքային տվյալների վատագույն տարբերակօ դեպքում — θ(n²).
== Ալգորիթմների բնութագրման լեզու
Մուտք: 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--;
}
}
}