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

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

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

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

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

  • Ժամանակը՝ հիմնական պարամետրը, բնութագրող ալգորիթմի արագությունը, անվանվում է նաև հաշվողական դժվարություն: Թվարկման համար կարևոր է ալգորիթմի վատագույն, միջին և լավագույն պահվածքը մուտքային բազմության A հզորության տերմիններով։ Եթե ալգորիթմի մուտքին տրվում է բազմաթիվ A, ապա կնշանակենք n = |A|: Տիպիկ ալգորիթմի համար լավ տարբերակը դա՝ O \left(n \log n \right)[1] ն է և վատ տարբերակը դա ՝ 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(n2), ինդեքսի յուրաքանչյուր զույգի համար իրականացվում է փոխանակում, եթե էլեմենտը տեղաբաշխված են ոչ հերթականությամբ։
  • Կոկտեյլային տեսակավորում ( Cocktail sort, bidirectional bubble sort) ` Ալգորիթմի դժվարություն` O(n2)
  • Գաճաճային տեսակավորումը ունի ընդհանրություն պղպջակային և մուտքային տեսակավորումների հետ։ Ալգորիթմի բարդությունը O(n2).
  • Մուտքային տեսակավորում (Insertion sort) , ալգորիթմի բարդությունը O(n2)։ Որոշում ենք որտեղ պետք է ընթացիկ էլեմենտը գտնվի հաջորդական տեսքով և դնում ենք դրան այնտեղ :
  • Բլոկային տեսակավորում (զամբյուղային տեսակավորում 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(n2); ամենամեծ կամ ամենափոքր էլեմենտի փնտրումև նրա տեղադրումը հաջորդականացված ցանկի վերջում կամ սկզբում
  • Շելլի տեսակավորում (Shell sort) ալգորիթմի դժվարությունը ` O(n log2 n); և փորձ լավացնելու մուտքային տեսակավորումը
  • Սանրային տեսակավորում (Comb sort) ալգորիթմի բարդությունը ՝ O(n log n)
  • Խմբային տեսակավորում (Heapsort) ալգորիթմի բարդությունը ՝ O(n log n) ՝ վերածում ենք ցանկը խմբի, վերցնում ենք ամենամեծ էլեմենտը և ավելացնում ենք ցանկի ամենավերջը :
  • Հարթ տեսակավորում (Smoothsort) ալգորիթմի բարդությունը ՝ O(n log n)
  • Արագ տեսակավորում (Quicksort), հիշողության նվազագույն ծախս , ալգորիթմի բարդությունը O(n log n) միջին ժամանակը, O(n2) վատագույն դեպք, լայն տարածում ունի որպես ամենաարագը դասավորելու մեծ պատահական ցանկերի համար՝ բաժանելով 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(nk); անհրաժեշտ է O(k) լրացուցիչ հիշողություն։

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

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

Տեսակավորման այլ ալգորիթմներ[խմբագրել]

Տես նաև[խմբագրել]

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

  • Դոնալդ Կնուտ // Ծրագրավորման արվեստ , հատոր 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.

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

Կաղապար:Նշում

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

Կաղապար:Վիկիգիրք

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

  1. O-նշագրում