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

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

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

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

• Ժամանակը՝ հիմնական պարամետրը, բնութագրող ալգորիթմի արագությունը, անվանվում է նաև հաշվողական դժվարություն: Թվարկման համար կարևոր է ալգորիթմի վատագույն, միջին և լավագույն պահվածքը մուտքային բազմության $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<sup>2</sup>), ինդեքսի յուրաքանչյուր զույգի համար իրականացվում է փոխանակում, եթե էլեմենտը տեղաբաշխված են ոչ հերթականությամբ:
• Կոկտեյլային տեսակավորում ( Cocktail sort, bidirectional bubble sort) ` Ալգորիթմի դժվարություն` O(n<sup>2</sup>)
• Գաճաճային տեսակավորումը ունի ընդհանրություն պղպջակային և մուտքային տեսակավորումների հետ: Ալգորիթմի բարդությունը O(n<sup>2</sup>).
• Մուտքային տեսակավորում (Insertion sort) , ալգորիթմի բարդությունը O(n<sup>2</sup>): Որոշում ենք որտեղ պետք է ընթացիկ էլեմենտը գտնվի հաջորդական տեսքով և դնում ենք դրան այնտեղ :
• Բլոկային տեսակավորում (զամբյուղային տեսակավորում 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. տեսակավորում և փնտրում // {{{վայր}}}. — ISBN 5-8459-0082-4.
• Թոմաս.Հ. Կորմեն, Չառլզ Ի.Լեյզերսոն, Ռոնալդ Լ.Ռիվեստ, Կլիֆորդ Շտայն // Ալգորիթմներ ՝ կառուցվածքը և անալիզ // Կաղապար:Մ.. — ISBN 5-8459-0857-4.
• Ռոբերտ Սեդջվիք // Հիմնական ալգորիթմներ Ս. Անալիզի /Տվյալների կառուցվածք /Տեսակավորում/Փնտրում // Կաղապար:ՍՊբ.. — ISBN 5-93772-081-4.

Հղումներ

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

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