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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Շելլի տեսակավորում ալգորիթմ գունավոր բարեր

Շելլի տեսակավորումը (անգլ.՝ 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

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

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

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