Jump to content

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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Շելլի տեսակավորում
Տեսակտեսակավորման ալգորիթմ, in-place algorithm? և համեմատություններով դասակարգում
Դաստեսակավորման ալգորիթմ
Տվյալների կառուցվածք[1]
Վատագույն դեպքում կատարումը[2]
Լավագույն դեպքում կատարումը[1]
Օգտագործում էզանգված
ՀայտնաբերողDonald Shell?[3]
Շելլի տեսակավորում ալգորիթմ գունավոր բարեր

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

Նկարագրություն

[խմբագրել | խմբագրել կոդը]

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

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

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

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

Ենթադրենք տրված է ցուցակ, և կատարվում է այս ցուցակի տեսակավորումը Շելլի մեթոդով, իսկ որպես նշանակաություն տրված են ։

Առաջին քայլում տեսակավորվում են - գրվածքները։ -ի մեջ ընդգրկված բոլոր էլեմենտները, բաժանվում են 5 մասի։ Այսինքն , , , , .

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

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

Ժամանակահատվածների ընտրությունը

[խմբագրել | խմբագրել կոդը]

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

  • Ի սկզբանե Շելլի կողմից օգտագործվող ժամամանակահատվածների երկարության հաջորդականությունը այսպիսին էր՝ վատագույն դեպքում, ալգորիթմի դժվարությունը կայանում է՝ -ում;
  • Հիբբարդի կողմից առաջարկած հաջորդականությունը հետևյալն է՝ բոլոր արժեքները։ Քայլերի մնան հաջորդականությունը բերում է բարդության ալգորիթմի;
  • Սեդժիկի կողմից առաջարկած հաջորդականությունը հետևյալն է՝ , եթե i-ն հաշվելի է և , եթե i-ն անվերջ է։ Քայլերի նման հաջորդականության դեպքում ալգորիթմի միջին դժվարությունը կայանում է՝ -ում, դասավորվածության վատագույն դեպքում՝ : Սեդժիկի բանաձևի օգտագործման ժամանակ պետք է կանգ առնել inc[s-1] արժեքի վրա, եթե 3*inc[s] > size.[4];
  • Պրատտի կողմից առաջարկած հաջորդականությունը հետևյալն է՝ բոլոր արժեքները։ Այս դեպքում ալգորիթմի դյժարություն կայանում է -ում;
  • Մարցին Ցիուրի առաջարկած էմպիրիկ հաջորդականությունը՝(A102549-ի հաջորդականությունը OEIS-ում)։ ; հանդիսանում է լավագույններից մեկը, մոտավորապես մինչև 4000 էլեմենտների տեսակավորման կարողությամբ։.[5];
  • Ֆիբոնատտիի թվերի վրա հիմնված էմպիրիկ հաջորդականությունը `;
  • [փա՞ստ] բոլոր արժեքները, ։ Քայլերի նման հաջորդականությունը բերում է` բարդության ալգորիթմի։

Ծանոթագրություններ

[խմբագրել | խմբագրել կոդը]
  1. 1,0 1,1 https://www.cs.wcupa.edu/rkline/ds/shell-comparison.html
  2. Pratt V. R. Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences)ISBN 978-0-8240-4406-0
  3. Shell D. L. A high-speed sorting procedure // Commun. ACM[New York]: Association for Computing Machinery, 1959. — Vol. 2, Iss. 7. — P. 30—32. — ISSN 0001-0782; 1557-7317doi:10.1145/368370.368387
  4. J. Incerpi, R. Sedgewick, «Improved Upper Bounds for Shellsort», J. Computer and System Sciences 31, 2, 1985.
  5. «Marcin Ciura Best Increments for the Average Case of Shellsort» (PDF). Արխիվացված է օրիգինալից (PDF) 2011 թ․ օգոստոսի 30-ին. Վերցված է 2011 թ․ մայիսի 21-ին.

Արտաքին հղումներ

[խմբագրել | խմբագրել կոդը]