Տեսակավորման ալգորիթմ

Տեսակավորման ալգորիթմ
Դաս	կոմբինատորային ալգորիթմ

Համակարգչային գիտություններում տեսակավորման ալգորիթմը ալգորիթմ է, որը դասավորում է էլեմենտները ցանկից որոշակի կարգով։ Այն դեպքում, երբ ցանկի էլեմենտը ունի մի քանի դաշտ, ապա այդ դաշտը, որը համարվում է հաջորդականության կրիտերիա, անվանվում է տեսակավորման բանալի։ Պրակտիկայում բանալու փոխարեն հաճախ հանդիսանում է թիվը, իսկ մնացած դաշտերում պահվում են որևիցե տվյալներ, որոնք ոչ մի կերպ չեն ազդում ալգորիթմի աշխատանքի վրա։

Տեսակավորման ալգորիթմի գնահատում

Տեսակավորման ալգորիթմները գնահատվում են կատարման արագությամբ և հիշողության օգտագործման արդյունավետությամբ։

• Ժամանակը՝ հիմնական պարամետրը, բնութագրող ալգորիթմի արագությունը, անվանվում է նաև հաշվողական դժվարություն։ Թվարկման համար կարևոր է ալգորիթմի վատագույն, միջին և լավագույն պահվածքը մուտքային բազմության $A$ հզորության տերմիններով։ Եթե ալգորիթմի մուտքին տրվում է բազմաթիվ $A$, ապա կնշանակենք $n=|A|$։ Տիպիկ ալգորիթմի համար լավ տարբերակը դա՝ $O\left(n\log n\right)$ ն է և վատ տարբերակը դա ՝ $O\left(n^{2}\right)$ ն է։ Հաջորդականության համար կատարյալ տարբերակը դա՝ $O\left(n\right)$ն է։ Տեսակավորման ալգորիթմները, օգտագործող բանալիների համեմատման աբստրակտ օպերացիա՝ միշտ կարիք ունեն նվազագույնը $\Omega \left(n\log n\right)$ համեմատության։ Ինչևիցե, գոյություն ունի տեսակավորման Հանա ալգորիթմ (Yijie Han) ՝ $O\left(n\cdot \log \log n\cdot \log \log \log n\right)$ հաշվողական դժվարությամբ, օգտագործող այն փաստը, որ բանալիների տարածքը սահմանափակ է (Այն չափից շատ բարդ, իսկ О-նշանակության հետևը թաքնված է շատ մեծ գործակից, որը նրա օգտագործումը դարձնում է անհնարին ամենօրյա պրակտիկայում)։ Նաև գոյություն ցանցեր տեսակավորող հասկացությունը։ Ենթադրելով, որ հնարավոր է միաժամանակ (օրինակ, զուգահեռ հաշվարկման դեպքում) անցկացնել մի քանի համեմատություն, կարելի է տեսակավորել $n$ թվերը $O\left(\log ^{2}n\right)$ օպերացիաներով։ Բացի այդ $n$ թիվը պետք է նախօրոք հայտնի լինի։
• Հիշողություն ՝ մի շարք ալգորիթմներ կարիք ունի լրացուցիչ հիշողության տվյալների ժամանակավոր պահպանման համար։ Որպես կանոն այդ ալգորիթմները պահանջում են $O\left(\log n\right)$ հիշողություն։ Գնահատման ժամանակ չի հաշվարկվում տեղը, որը զբաղեցնում է առաջնային մասսիվը և մուտքային հաջորդականությունից անկախ ծախսերը, օրինակ, ծրագրի կոդի պահպանման համար (քանի, որ այս ամենը օգտագործում է $O\left(1\right)$)։ Տեսակավորման ալգորիթմները, չօգտագործող ավելորդ հիշողություն, համարում են տեղում տեսակավորման"։

Տեսակավորման ալգորիթմների դասակարգումը

• Կայունությունը (stability) - կայուն տեսակավորումը չի փոխում հավասար էլեմենտների փոխադարձ տեղակայումը։
• Բնական պահվածք , դա մեթոդի արդյունավետությունն է արդեն հերթականությամբ դրված, կամ մասնակի հերթականացված տվյալների համար։ Ալգորիթմը իրեն բնական է պահում, եթե հաշվի է առնում մուտքային հաջորդականությունը և ավելի լավ է աշխատում։

Համեմատման օպերացիաների օգտագործում. Ալգորիթմները, օգտագործող տեսակավորելու համեմատման էլեմենտները իրար միջև կոչվում են համեմատության վրա հիմնավորված։ Վատագույն պատահարի նվազագույն աշխատատարությունը կազմում է $O\left(n\log n\right)$, բայց սրանք տարբերվում են օգտագործման ճկունությամբ։ Հատուկ դեպքերի համար (տվյալների տիպեր) գոյություն ունի ավելի արդյունավետ ալգորիթմներ։

Ալգորիթմի ևս մեկ կարևոր հատկություն է համարվում նրա օգտագործման միջավայրը։ Այստեղ հաջորդականացման երկու տեսակ կա՝

• Ներքին տեսակավորում աշխատում է մասսիվների հետ, ամբողջությամբ գտնվող օպերատիվ հիշողության մեջ ազատ մուտքով ցանկացած արկղիկին։ Տվյալները սովորաբար հաջորդականացվում են նույն տեղում, առանց ավելորդ ծախսերի։
  • Ժամանակակից անձնական համակարգիչների ճարտարագիտությունում լայն տարածում ունի ներբեռնում և քեշավորում հիշողությունը։ Տեսակավորման ալգորիթմը պետք է լավ համապատասխանի քեշավորման և ներբեռնման ալգորիթմների հետ։
• Արտաքին տեսակավորում աշխատում է մեծ ծավալ ունեցող հիշող սարքերի հետ, բայց ոչ ազատ մուտքով, այլ հաջորդականությամբ (ֆայլերի հաջորդականացում), այսինքն տվյալ պահին մենք 'տեսնում ենք' միայն մեկ էլեմենտ, իսկ ծախսերը շատ մեծ են։ Սա ալգորիթմի վրա դնում է որոշ լրացուցիչ սահմանափակումներ և բերում է հատուկ մեթոդների հաջորդականացման, որոնք հաճախ օգտագործում են լրացուցիչ սկավառակային տարածք։ Բացի այդ կրիչի տվյալների մուտքի համար ավելի կամաց է լինում, քան օպերատիվ հիշողությամբ օպերացիաները։
  • Մուտքը կրիչին իրականանում է հաջորդական տեսքով՝ ամեն պահի հնարավոր է հաշվել կամ ձայնագրել միայն այն էլեմենտը, որը ընթացիկի հաջորդն է։

Ալգորիթմները նաև դասակարգվում են՝

• լրացուցիչ հիշողության կարիք կամ դրա բացակայությունը
• Տվյալների կառուցվածքի իմացության կարիք, համեմատման օպերացիայի սահմաններից դուրս, կամ դրա բացակայությունը։

Տեսակավորման ալգորիթմների ցանկ

Այս աղյուսակում n գրվածքների քանակն է, որոնք անհրաժեշտ է հաջորդականացնել, իսկ k յուրահատակ բանալիների քանակն է։

Կայուն ալգորիթմների տեսակավորում

• Պղպջակային տեսակավորում (անգլ.՝ Bubble sort ) , ալգորիթմի դժվարություն՝ O(n²), ինդեքսի յուրաքանչյուր զույգի համար իրականացվում է փոխանակում, եթե էլեմենտը տեղաբաշխված են ոչ հերթականությամբ։
• Կոկտեյլային տեսակավորում ( Cocktail sort, bidirectional bubble sort) ` Ալգորիթմի դժվարություն` O(n²)
• Գաճաճային տեսակավորումը ունի ընդհանրություն պղպջակային և մուտքային տեսակավորումների հետ։ Ալգորիթմի բարդությունը O(n²).
• Մուտքային տեսակավորում (Insertion sort) , ալգորիթմի բարդությունը O(n²)։ Որոշում ենք որտեղ պետք է ընթացիկ էլեմենտը գտնվի հաջորդական տեսքով և դնում ենք դրան այնտեղ։
• Բլոկային տեսակավորում (զամբյուղային տեսակավորում Bucket sort) ալգորիթմի դժվարությունը ` O(n), պետք է O(k) լրացուցիչ հիշողություն և տեսակավորվող տվյալների էության իմացություն , "տեղափոխել" և "համեմատել" ֆունկցիաների սահմանների մեջ։
• Հաշվարկող տեսակավորում (Counting sort) ալգորիթմի բարդությունը ` O(n+k);անհրաժեշտ է O(n+k) լրացուցիչ հիշողություն (ուսումնասիրվել է 3 տարբերակ)
• Միաձուլման տեսակավորում (Merge sort) ալգորիթմի բարդությունը` O(n log n); անհրաժեշտ է O(n) լրացուցիչ հիշողություն;շարում ենք ցանկի առաջին և երկրորդ մասը առանձին, իսկ հետո միաձուլում ենք հաջորդականացված ցանկերը։
• Ծառային տեսակավորում (անգլ.՝ Tree sort) ալգորիթմի բարդությունը՝ O(n log n);անհրաժեշտ է O(n) լրացուցիչ հիշողություն։

Ալգորիթմի ոչ կայուն տեսակավորում

• Ընտրանքային տեսակավորում (Selection sort) ալգորիթմի բարդությունը ` O(n<sup>2</sup>); ամենամեծ կամ ամենափոքր էլեմենտի փնտրումև նրա տեղադրումը հաջորդականացված ցանկի վերջում կամ սկզբում
• Շելլի տեսակավորում (Shell sort) ալգորիթմի դժվարությունը ` O(n log² n); և փորձ լավացնելու մուտքային տեսակավորումը
• Սանրային տեսակավորում (Comb sort) ալգորիթմի բարդությունը ՝ O(n log n)
• Խմբային տեսակավորում (Heapsort) ալգորիթմի բարդությունը ՝ O(n log n) ՝ վերածում ենք ցանկը խմբի, վերցնում ենք ամենամեծ էլեմենտը և ավելացնում ենք ցանկի ամենավերջը։
• Հարթ տեսակավորում (Smoothsort) ալգորիթմի բարդությունը ՝ O(n log n)
• Արագ տեսակավորում (Quicksort), հիշողության նվազագույն ծախս, ալգորիթմի բարդությունը O(n log n) միջին ժամանակը, O(n²) վատագույն դեպք, լայն տարածում ունի որպես ամենաարագը դասավորելու մեծ պատահական ցանկերի համար՝ բաժանելով 2 մասի սկզբնական տվյալները, այնպես, որ առաջին կեսի ցանկացած էլեմենտ դասավորված է երկրորդ կեսի ցանկացած էլեմենտի համեմատ։ Հետո ալգորիթմը օգտագործվում է ռեկուրսիվ ամեն կեսում։ O(n) լրացուցիչ հիշողության դեպքում, կարելի է տեսակավորումը ավելի կայուն անել։
• Ներքին տեսակավորում ալգորիթմի բարդություն ՝ O(n log n)։ Սա արագ և խմբային տեսակավորման խառնուրդ է։ Խմբային տեսակավորումը օգտագործվում է այն դեպքում, երբ ռեկուրսիայի խորությունը գերազանցում է log(n)-ը։
• Համբերության տեսակավորում ալգորիթմի բարդություն ՝ O(n log n) ամենավատ տարբերակը կարիք ունի O(n) հիշողության, նաև գտնում է ամենաերկար մեծացող ենթահաջորդականությունը
• Կամակատարի տեսակավորում ռեկուրսիվ ալգորիթմ է ժամանակային $O(n^{\log _{1{,}5}{3}})\approx O(n^{2.71})$ բարդությամբ։
• Արմատային տեսակավորում ալգորիթմի բարդությունը ՝ O(n•k); անհրաժեշտ է O(k) լրացուցիչ հիշողություն։

Տեսակավորման ոչ արդյունավետ ալգորիթմներ

• Ճահճային տեսակավորում O(n•n!) ՝ միջինում։ Ազատորեն խառնել մասսիվը, ստուգել հերթականությունը։
• Տեղափոխմամբ տեսակավորում O(n•n!) ՝ վատագույն տարբերակն է։ Յուրաքանչյուր զույգի համար իրականացվում է ճիշտ հերթականության ստուգում և գեներացվում է սկզբնական մասսիվի բոլոր հնարավոր տեղափոխությունները։
• Հիմար տեսակավորում (Stupid sort) O(n³); ռեկուրսիվ տարբերակը կարիք ունի O(n²) հիշողության։
• Կաթիլային տեսակավորում O(n) կամ O(√n), անհրաժեշտ է հատուկ ապարատային ապահովում։
• Բլիթային տեսակավորում (Pancake sorting) O(n), անհրաժեշտ է հատուկ ապարատային ապահովում։

Ալգորիթմներ չհիմնավորված համեմատության վրա

• Բլոկային տեսակավորում (Bucket sort)
• լեքսիկոգրաֆիկ կամ արմատային տեսակավորում (Radix sort)
• Հաշվողական տեսակավորում (Counting sort)

Տեսակավորման այլ ալգորիթմներ

• Տոպոլոգիական տեսակավորում
• Արտաքին տեսակավորում

Տես նաև

• O-Մեծ
• Ալգորիթմի ժամանակային բարդություն
• Ալգորիթմի տարողականության դժվարություն
• Արտաքին տեսակավորում
• Տեսակավորող ցանցեր
• Համեմատություն
• Շվարցի տրանսֆորմացիա
• Զուգահեռ տեսակավորում
• Ինդեքսային տեսակավորում

Գրականություն

• Դոնալդ Կնուտ, Ծրագրավորման արվեստ , հատոր 3. տեսակավորում և փնտրում 824, էջեր 824 — 824 էջ, ISBN 5-8459-0082-4։
• Թոմաս.Հ. Կորմեն, Չառլզ Ի.Լեյզերսոն, Ռոնալդ Լ.Ռիվեստ, Կլիֆորդ Շտայն, Ալգորիթմներ ՝ կառուցվածքը և անալիզ, М. 1296, էջեր 1296 — 1296 էջ, ISBN 5-8459-0857-4։
• Ռոբերտ Սեդջվիք, Հիմնական ալգորիթմներ Ս. Անալիզի /Տվյալների կառուցվածք /Տեսակավորում/Փնտրում, Կաղապար:ՍՊբ. 672, էջեր 672 — 672 էջ, ISBN 5-93772-081-4։

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

• Տեսակավորման ալգորիթմներ algolist.manual.ru
• Տեսակավորված ալգորիթմների անիմացված համեմատում (անգլ.)