Շելլի տեսակավորում

Վիքիպեդիայից՝ ազատ հանրագիտարանից

Շելլի տեսակավորումը (անգլ.՝ Shell sort) — տեսակավորման ալգորիթմ, հանդիսանում է ներդրմամբ տեսակավորման կատարելագործված տեսակը:Շելլի մեթոդի գաղափարն այն է, որ իրար հետ կարող են համեմատվել ոչ միայն կողք կողքի գտնվող տարրեը, այլ նաև նրանք, որոնք գտնվում են իրարից որոշակի հեռավորության վրա:Այլ կերպ ասած դա հենց ներդրմամբ տեսակավորումն է`նախնական «կոպիտ» անցումներով: Պղպջակային տեսակավորման անալոգային մեթոդը կոչվում է սանրային տեսակավորում:

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

Շելլի տեսակավորման ժամանակ իրար հետ համեմատվում և տեսակավորվում են այն արժեքները , որոնք գտնվում են իրարից որոշակի d հեռավորության վրա (տես.ներքևում):Դրանից հետո այդ գործընթացը կրկնվում է d -ի ավելի փոքր արժեքների համար, իսկ տեսակավորումն ավարտվում է, երբ d=1 (այսինքն սովորական ներդրմամբ տեսակավորում):Շելլի տեսակավորման էֆֆեկտիվությունը որոշ դեպքերում կայանում է նրանում, որ տարրերը ավելի արագ են դասավորվում իրենց տեղերում (տեսակավորման հասարակ մեթոդների ժամանակ, օրինակ պղպջակային, երկու էլեմենտի յուրաքանչյուր տեղաշարժը փոքրացնում է ինվերսիաների քանակը ցանկում առավելագույնը 1-ով, իսկ Շելլի տեսակավորման ժամանակ այդ թիվը կարող է ավելի շատ լինել):

Չնայած նրան, որ Շելլի տեսակավորումը շատ դեպքերում ավելի դանդաղ է, քան արագ տեսակավորումը, այն ունի որոշակի առավելություններ.

  • Պահանջարկի բացակայությունը հիշողության գրապահոցում,
  • դեգրադացիայի բացակայությունը տվյալների անհաջող հավաքածուի դեպքում — արագ տեսակավորումը հեշտ դեգրադացվում է մինչև O(n²), որն ավելի վատ է, քան Շելլի տեսակավորման համար ապահովագրած ամենավատ ժամանակը :

Պատմությունը[խմբագրել]

Շելլի տեսակավորումը անվանլելի է նրա հեղինակի — Դոնալդ Շելլի պատվին, որը հրապարակել է այս ալգորիթմը 1959թ-ին:Որոշ երկրներում այս ալգորիթմը անվանում են Շելլ-Մեցների ալգորիթմ Մառլեն Մենցեր-Նորտոնի պատվին: Սակայն հետագայում Մենցերը հերքել է դա` ասելով. «Ես ոչ մի առնչություն չունեմ այդ տեսակավորման հետ , և իմ անունը երբեք չպետք է կապվի դրա հետ»:

Օրինակ[խմբագրել]

Shellsort-ru.svg


Ենթադրենք տրված է A = (32, 95, 16, 82, 24, 66, 35, 19, 75, 54, 40, 43, 93, 68) ցուցակ, և կատարվում է այս ցուցակի տեսակավորումը Շելլի մեթոդով , իսկ որպես d նշանակաություն տրված են 5, 3, 1:

Առաջին քայլում տեսակավորվում են A - գրվածքները: A-ի մեջ ընդգրկված բոլոր էլեմենտները , բաժանվում են 5 մասի: Այսինքն A_{5,1} = (32, 66, 40), A_{5, 2} = (95, 35, 43), A_{5, 3} = (16, 19, 93), A_{5, 4} = (82, 75, 68), A_{5, 5} = (24, 54).

Երկրորդ քայլում նույնպես կատարվում է ստացված ցուցակի տեսակավորումը, սակայն մնացած գրվածքները արդեն բաժանվում են 3 մասի:

Ցանկի տեսակավրումը ավարտվում է սովորական ներդրման տեսակավորմամբ:

Ժամանակահատվածների ընտրությունը[խմբագրել]

Ալգորիթմի աշխատանքի միջին ժամանակը կախված է d ժամանակահատվածների երկարություններից , որոնց վրա հետագայում պետք է գտնվեն N կարողությամբ զանգվածի տեսակավորվող տարրերը :Գոյություն ունեն այդ արժեքների ընտրության մի քանի մոտեցումներ.

  • իսկզբանե Շելլի կողմից օգտագործվող ժամամանակահատվածների երկարության հաջորդականությունը այսպիսին էր` ~d_1 = N/2,  d_i = d_{i-1} / 2,  d_0 = 1 վատագույն դեպքում, ալգորիթմի դժվարությունը կայանում է` c N^2-ում;
  • Հիբբարդի կողմից առաջարկած հաջորդականությունը հետևյալն է` ~(2^i-1)/2 \le N/2, i \in \mathbb N բոլոր արժեքները: Քայլերի մնան հաջորդականությունը բերում է O(N^{3/2}) բարդության ալգորիթմի;
  • Սեդժիկի կողմից առաջարկած հաջորդականությունը հետևյալն է` ~d_i = 9\cdot2^i - 9\cdot2^{i/2} + 1, եթե i-ն հաշվելի է և ~d_i = 8\cdot2^i - 6\cdot2^{(i+1)/2} + 1, եթե i-ն անվերջ է:Քայլերի նման հաջորդականության դեպքում ալգորիթմի միջին դժվարությունը կայանում է` O(n^{7/6})-ում, դասավորվածության վատագույն դեպքում` O(n^{4/3}): Սեդժիկի բանաձևի օգտագործման ժամանակ պետք է կանգ առնել inc[s-1] արժեքի վրա, եթե 3*inc[s] > size.[1];
  • Պրատտի կողմից առաջարկած հաջորդականությունը հետևյալն է` ~2^i\cdot3^j \le N/2, i, j \in \mathbb N բոլոր արժեքները: Այս դեպքում ալգորիթմի դյժարություն կայանում է O(N (log N)^2)- ում;
  • Մարցին Ցիուրի առաջարկած էմպիրիկ հաջորդականությունը`(A102549-ի հաջորդականությունը OEIS-ում): ~d \in \left\{1, 4, 10, 23, 57, 132, 301, 701, 1750\right\}; հանդիսանում է լավագույններից մեկը, մոտավորապես մինչև 4000 էլեմենտների տեսակավորման կարողությամբ:.[2];
  • Ֆիբոնատտիի թվերի վրա հիմնված էմպիրիկ հաջորդականությունը `~d \in \left\{F_n\right\};
  • ~(3^j-1)/2 \le N/2 Կաղապար:Нет АИ բոլոր արժեքները, j \in \mathbb N: Քայլերի նման հաջորդականությունը բերում է` O(N^{3/2}) բարդության ալգորիթմի:

Նշումներ[խմբագրել]

  1. J. Incerpi, R. Sedgewick, «Improved Upper Bounds for Shellsort», J. Computer and System Sciences 31, 2, 1985.
  2. Marcin Ciura Best Increments for the Average Case of Shellsort

Հղումներ[խմբագրել]

Վիքիդարանի պատկերանիշը
Անգլերեն Վիքիդարանում կան նյութեր այս թեմայով՝
Շելլի տեսակավորում

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

Категория:Տեսակավորման ալգորիթմեր