Արագ տեսակավորում

**Արագ տեսակավորում** () հաճախ անվանում են qsort C լեզվի ստանդարտ գրադարանի իրականացման անունով։ Այն հայտնի դասակարգման ալգորիթմ է, որը մշակվել է անգլիացի ինֆորմատիկ Չարլզ Հոարի կողմից 1960 թվականին։ Զանգվածի տեսակավորման առաջին արագ ունիվերսալ ալգորիթմն է։ *n* հատ տարրերի տեսակավորման համար կատարում է միջինը O (*n*&nbsp;log&nbsp;*n*) համեմատություն։ Ամենավատ դեպքում կատարում է O(*n*2) համեմատություն, չնայած այսպիսի բան պատահում է հազվադեպ։ Quicksort-ը հաճախ ավելի արագ է գործում, քան այլ O(*n*&nbsp;log&nbsp;*n*) ալգորիթմները։

## Ալգորիթմի հակիրճ նկարագրությունը
*QuickSort*-ը ներկայացնում է անմիջական փոփոխման միջոցով ալգորիթմի տեսակավորման զգալիորեն բարելավված տարբերակ ( դրա տարբերակներն են «Պղպջակային տեսակավորումը» և « Թափահարման տեսակավորումը») , որը հայտնի է նաև իր ցածր արդյունավետությամբ։ Հիմնական տարբերությնն այն է, որ առաջին հերթին արվում եմ ամենամեծ հեռավորությունների վերադասավորումները և յուրաքանչյուր անցումից հետո էլեմենտները բաժանվում են երկու ինքնուրույն խմբերի։ Հետաքրքիր է, որ ամենաանարդյունավետ անմիջական տեսակավորման մեթոդի բարելավման արդյունքում ստեղծվեց ամենաարդյունավետ բարելավված մեթոդը։
 
Ալգորիթմի ընդհանուր միտքը հետևյալում է՝
* Ընտրել մատրիցայի անդամներից հենակետայինը, որը կարող է լինել ցանկացած էլեմենտ։
* Համեմատել մյուս էլեմենտները հենակետայինի հետ և դրանք դասավորել մատրիցայում այնպես, որ մատրիցան բաժանվի երեք շարունակական, մեկը մյուսին հաջորդող հատվածների հենակետայինից փոքր, հավասար և մեծ։
* «Մեծ» և «Փոքր» հատվածների համար կատարել գործողությունների նույն հաջորդականությունները, եթե հատվածի երկարությունը մեծ է մեկից։
Գործնականում մատրիցան բաժանվում է ոչ թե երեք, այլ երկու հատվածների՝ « հենակետայինից փոքր», «մեծ և հավասար»։ Այսպիսի մոտեցումն առավել արդյունավետ է, քանզի պարզեցնում է ալգորիթմի առանձնացումը։
Հոարը ստեղծեց այս մեթոդը մեքենայական թարգմանության կիրառմամբ։ Բառարանը պահվում էր մագնիսական ժապավենի վրա և մշակվող տեքստի բառերի ճիշտ դասակարգումը թույլ էր տալիս ստանալ դրանց թարգմանությունները մեկ ժապավենի վրա։ Հոանը հնարեց այս ալգորիթմը Խորհրդային Միությունում մնալու ընթացքում, երբ Մոսկվայի համալսարանում սովորում էր համակարգչային թարգմանություն և զբաղվում էր ռուս- անգլերեն զրուցարանի ստեղծմամբ։

## Ալգորիթմ
Արագ տեսակավորումը օգտագործում է «Բաժանիր և տիրիր (ալգորիթմ)» ստրատեգիան։ Ալգորիթմի քայլերի հաջորդականությունը հետևյալն է՝
# Ընտրում ենք զանգվածից մի քանի էլեմենտ, որոնք պետք է անվանենք հենակետային էլեմենտ։ Ալգորիթմի կոռեկտության տեսանկյունից հենակետային էլեմենտի ընտրությունը անկարևոր է։ Ալգորիթմի էֆեկտիվության բարձրացման տեսանկյունից պետք է ընտրվի մեդիանան, բայց առանց լրացուցիչ տեսակավորված տվյալների հնարավոր չէ տեղեկություն ստանալ։ Հայտնի ստրատեգիա է՝ մշտապես ընտրել միևնույն էլեմենտը, օրինակ մեջտեղի կամ վերջին զետեղվածը, ընտրել պատահական ինդեքսով ընտրված էլեմենտ։
# Զանգվածից բաժանման օպերացիան՝ վերակազմել զանգվածը այնպես, որպեսզի բոլոր էլեմենտները փոքր կամ հավասար գտնվեն հենակետային էլեմենտից ձախ, իսկ հենակետայինից մեծը՝ նրանից աջ։ Օպերացիայի ալգորիթմն է՝
## 2 ինդեքսներ - l և r, հավասարվում են բաժանվող զանգվածի մաքսիմալ և մինիմալ ինդեքսին։
## Առանձնացվում է ինդեքսի m հենակետային էլեմենտը։
## Ինդեքս l-ին մեծանում է մինչև m-ը այնքան ժամանակ, քանի դեռ l էլեմենտը չի գերազանցել հենակետայինին։
## Ինդեքս r-ը փոքրանում է մինչև m-ը այնքան ժամանակ, քանի դեռ r էլեմենտը չի թվացել փոքր կամ հավասար հենակետայինին։
## Եթե r = l - գտնվում է զանգվածի մեջտեղում - բաժանման օպերացիան ավարտված է, 2 ինդեքսներն էլ ցույց են տալիս հենակետային էլեմենտը։
## Եթե l N = 2CN/2+N, որի արտահայտության բացահայտ օրինակ է N lg N հավասարւմը։ Դա կտա տեսակավորման ավելի քիչ ժամանակ։
* **Միջին** Տալիս է միջինը O(*n*&nbsp;lg&nbsp;*n*) կարգավորված *n* էլեմենտների փոխանակում։ Իրականում հենց այդպիսի իրավիճակը ունենում է էլեմենտների պատահական կարգ և էլեմենտների զանգվածի մեջտեղից հենակետային էլեմենտների ընտրությունը պատահական է։ Պրակտիկայում արագ տեսակավորումը ավելի արագ է, քան մնացած ալգորիթմները O(*n*&nbsp;lg&nbsp;*n*), այն պատճառով, որ ալգորիթմի ներքին ցիկլը կարող է ցանկացած շինարարության մեջ կիրառվել։ 2CN/2 ծածկում է ստացված 2 զանգվածների տեսակավորման ծախսերը։ N- դա յուրաքանչյուր էլեմենտի վերամշակման գինն է։ Հայտնի է, որ այդ արտահայտությունը հավասար է CN = N lg N.ь։
* **Վատթարագույն դեպք** Վատթարագույն դեպքը կլինի այսպիսին, որի դեպքում յուրաքանչյուր էտապում զանգվածը հենակետային էլեմենտից կբաժանվի մի նոր զանգվածի։ Այդպիսի բան կարող է տեղի ունենալ, եթե վերամշակվածներից յուրաքանչյուր էտապում հենակետային ընտրվի կամ ամենամեծ կամ ամենափոքր էլեմենտը։

Վատ դեպք տալիս է O(*n*²) փոխանակումը։ Բայց փոխանակման քանակը և համապատասխանաբար աշխատանքի ժամանակը նրա ոչ մեծ թերությունն է։ Վատը այն է, որ այդ դեպքում ռեկուրսիայի խորությունը ալգորիթմի կատարման ժամանակ հասնում է n, որը կնշանակի n համառոտակի հետադարձ հասցեի պահպանում։ Լայն իմաստով n վատ դեպքը կարող է բերել հիշողության փչացման ալգորիթմի աշխատանքի ժամանակ։

## Բարելավում
* Տվյալ դիապազոնից հենակետային էլեմենտի ընտրության ժամանակ պատահական կերպով վատ դեպքը շատ քիչ հավանական է դառնում և ալգորիթմի տեսակավորման կատարման սպասված ժամանակը կլինի - O(*n*&nbsp;lg&nbsp;*n*).
* Ընտրել միջինը հենակետային 3 էլեմենտ (առաջին, միջին և վերջին)։ Այսպիսի ընտրությունը ուղղված է վատ պատահարի դեմ։
* Բաժանել զանգվածը ոչ թե 2, այլ 3 մասի։ (տես Dual Pivot Quicksort ).

## Առավելություններ և թերություններ
### Առավելություններ
* Ամենաարագագործ ալգորիթմներից մեկը ներքին տեսակավորման ընդհանուր (պրակտիկայում) նշանակության
* Պարզ է իրականացման մեջ։
* Ընդամենը պահանջում է O(\lg n) լրացուցիչ հիշողություն իր աշխատանքի համար։
* Հեշտ է համադրվում մեխանիզմների հետ քեշ հիշողություն և վերտուալ հիշողություն.
* Գոյություն ունի տողերի տեսակավորման էֆեկտիվ վերափոխություն (Սեդժվիկի ալգորիթմ) - սկզբում համեմատել հենակետային էլեմենտը զրոյական սիմվոլի տողի հետ, այնուհետև կիրառել անալոգային տեսակավորման համար «մեծ» և «փոքր» զանգվածներ, որոնք նույնպես համեմատել զրոյականի հետ, իսկ «հավասար» զանգվածը արդեն առաջին սիմվոլի հետ։

### Թերություններ
* Ուժեղ վատթարանում է արագությունը (մինչև \Theta(n^2)) հենակետային էլեմենտների անհաջող ընտրության ժամանակ, որը կարող է տեղի ունենալ անհաջող ելքային տվյալների մուտքագրման ժամանակ։ Դրանից կարելի է խուսափել՝ օգտագործելով այնպիսի վերափոխություն, ինչպիսին Introsort կամ հավանական է ընտրել պատահական հենակետային էլեմենտ, բայց ոչ ֆիքսված եղանակով։
* Ալգորիթմի իրականացումը կարող է բերել ստեկի գերհագեցման սխալի, այնպես ինչպես նրան կարող է անհրաժեշտ լինի կատարել O(n) ռեկուրսիվ ներդրման կանչեր։ Բարելավված իրականացումը, որում ռեկուրսիվ կանչերը տեղի են ունենում 2 զանգվածներից փոքրի տեսակավորման համար, ռեկուրսիայի խորությունը չի գերազանցում O(\lg n)։
* Կայուն - եթե պահանջվում է կայունություն՝ պետք է ընդլայնել բանալին։

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

## Արտաքին հղումներ
* Տեսակավորման ալգորիթմների անիմացիոն համեմատում
* Fast Sorting with Quicksort

Կատեգորիա:Դասակարգման ալգորիթմներ