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

Արագ տեսակավորում
	Պատահական դասավորված արժեքների արագ տեսակավորման ալգորիթմի անիմացիոն տարբերակը։ Կարմիր ձողերը հենակետային տարրերն են. Անիմացիոն գործողության սկզբում որպես հենակետային է ընտրվել ամենաաջում գտնվող տարրը։
Տեսակ	համեմատություններով դասակարգում, Բաժանիր և տիրիր (ալգորիթմ) և տեսակավորման ալգորիթմ
Դաս	տեսակավորման ալգորիթմ
Տվյալների կառուցվածք
Վատագույն դեպքում կատարումը
Լավագույն դեպքում կատարումը
Հայտնաբերող	Չարլզ Անտոնի Ռիչարդ Հոար

Արագ տեսակավորում (անգլ.՝ quicksort) հաճախ անվանում են qsort C լեզվի ստանդարտ գրադարանի իրականացման անունով։ Այն հայտնի դասակարգման ալգորիթմ է, որը մշակվել է անգլիացի ինֆորմատիկ Չարլզ Հոարի կողմից 1960 թվականին։ Զանգվածի տեսակավորման առաջին արագ ունիվերսալ ալգորիթմն է։ n հատ տարրերի տեսակավորման համար կատարում է միջինը O (n log n) համեմատություն։ Ամենավատ դեպքում կատարում է O(n²) համեմատություն, չնայած այսպիսի բան պատահում է հազվադեպ։ Quicksort-ը հաճախ ավելի արագ է գործում, քան այլ O(n log n) ալգորիթմները^[3]։

Ալգորիթմի հակիրճ նկարագրությունը

QuickSort-ը ներկայացնում է անմիջական փոփոխման միջոցով ալգորիթմի տեսակավորման զգալիորեն բարելավված տարբերակ ( դրա տարբերակներն են «Պղպջակային տեսակավորումը» և « Թափահարման տեսակավորումը») , որը հայտնի է նաև իր ցածր արդյունավետությամբ։ Հիմնական տարբերությնն այն է, որ առաջին հերթին արվում եմ ամենամեծ հեռավորությունների վերադասավորումները և յուրաքանչյուր անցումից հետո էլեմենտները բաժանվում են երկու ինքնուրույն խմբերի։ Հետաքրքիր է, որ ամենաանարդյունավետ անմիջական տեսակավորման մեթոդի բարելավման արդյունքում ստեղծվեց ամենաարդյունավետ բարելավված մեթոդը։

Ալգորիթմի ընդհանուր միտքը հետևյալում է՝

Ընտրել մատրիցայի անդամներից հենակետայինը, որը կարող է լինել ցանկացած էլեմենտ։
Համեմատել մյուս էլեմենտները հենակետայինի հետ և դրանք դասավորել մատրիցայում այնպես, որ մատրիցան բաժանվի երեք շարունակական, մեկը մյուսին հաջորդող հատվածների հենակետայինից փոքր, հավասար և մեծ։
«Մեծ» և «Փոքր» հատվածների համար կատարել գործողությունների նույն հաջորդականությունները, եթե հատվածի երկարությունը մեծ է մեկից։

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

Ալգորիթմ

Արագ տեսակավորումը օգտագործում է «Բաժանիր և տիրիր (ալգորիթմ)» ստրատեգիան։ Ալգորիթմի քայլերի հաջորդականությունը հետևյալն է՝

Ընտրում ենք զանգվածից մի քանի էլեմենտ, որոնք պետք է անվանենք հենակետային էլեմենտ։ Ալգորիթմի կոռեկտության տեսանկյունից հենակետային էլեմենտի ընտրությունը անկարևոր է։ Ալգորիթմի էֆեկտիվության բարձրացման տեսանկյունից պետք է ընտրվի մեդիանան, բայց առանց լրացուցիչ տեսակավորված տվյալների հնարավոր չէ տեղեկություն ստանալ։ Հայտնի ստրատեգիա է՝ մշտապես ընտրել միևնույն էլեմենտը, օրինակ մեջտեղի կամ վերջին զետեղվածը, ընտրել պատահական ինդեքսով ընտրված էլեմենտ։
Զանգվածից բաժանման օպերացիան՝ վերակազմել զանգվածը այնպես, որպեսզի բոլոր էլեմենտները փոքր կամ հավասար գտնվեն հենակետային էլեմենտից ձախ, իսկ հենակետայինից մեծը՝ նրանից աջ։ Օպերացիայի ալգորիթմն է՝
1. 2 ինդեքսներ - l և r, հավասարվում են բաժանվող զանգվածի մաքսիմալ և մինիմալ ինդեքսին։
2. Առանձնացվում է ինդեքսի m հենակետային էլեմենտը։
3. Ինդեքս l-ին մեծանում է մինչև m-ը այնքան ժամանակ, քանի դեռ l էլեմենտը չի գերազանցել հենակետայինին։
4. Ինդեքս r-ը փոքրանում է մինչև m-ը այնքան ժամանակ, քանի դեռ r էլեմենտը չի թվացել փոքր կամ հավասար հենակետայինին։
5. Եթե r = l - գտնվում է զանգվածի մեջտեղում - բաժանման օպերացիան ավարտված է, 2 ինդեքսներն էլ ցույց են տալիս հենակետային էլեմենտը։
6. Եթե l < r - գտնված զույգ էլեմենտները հարկավոր է փոխել տեղերով և շարունակել բաժանման օպերացիան մինչև l և r հասանելի լինեն։ Հարկավոր է հաշվել, որ եթե ինչ-որ սահման (l կամ r) հասել է մինչև հենակետային էլեմենտի, ապա m-ի փոխանակության իմաստը փոխվում է r կամ l էլեմենտի համապատասխանաբար։
Ռեկուրսիվ կարգավորում ենք զանգվածները հենակետային էլեմենտների աջ և ձախ կողմերում։
Ռեկուրսիայի բազան համարվում է հավաքածու, որը բաղկացած է մեկ կամ երկու էլեմենտներից։ Առաջինը վերադառնում է նախնական դիրքի, իսկ երկրորդ՝ անհրաժեշտության դեպքում, տեսակավորումը հասնում է 2 էլեմենտների վերադասավորմանը։

Հետաքրքիր է, որ Խոարը մշակել է այս մեթոդը մեքենայական թարգմանության կիրառմամբ։ Բանն այն է, որ այդ ժամանակ բառարանը պահվում էր մագնիսական ժապավենի վրա, և եթե կարգավորել տեքստի բոլոր բառերը՝ նրա թարգմանությունը կարելի էր ստանալ 1 լրիվ ժապավենի վրա։

Էֆեկտիվության գնահատական

QuickSort հանդիսանում է գոյություն ունեցող տեսակավորման ալգորիթմի կատարելագործված տարբերակ ուղիղ փոխանակության օգնությամբ (նրա տարբերակները հայտնի են ինչպես«Պղպջակային տեսակավորում», այդ թվում հայտնի է նաև իր ցածր էֆեկտիվությամբ։ Սկզբունքային տարբերությունն այն է, որ յուրաքանչյուր անցումից հետո էլեմենտները բաժանվում են 2 անկախ խմբերի։

Լավագույն դեպք Այդ ալգորիթմի համար լավագույն դեպքը, եթե յուրաքանչյուր կրկնապատկման ժամանակ յուրաքանչյուր զանգված բաժանվում է 2 հավասարամեծ զանգվածների։ Արագ տեսակավորման համեմատման արդյունքում հավասար կլինի ռեկուրսիվ արտահայտության իմաստին C_N = 2C_N/2+N, որի արտահայտության բացահայտ օրինակ է N lg N հավասարւմը։ Դա կտա տեսակավորման ավելի քիչ ժամանակ։
Միջին Տալիս է միջինը O(n lg n) կարգավորված n էլեմենտների փոխանակում։ Իրականում հենց այդպիսի իրավիճակը ունենում է էլեմենտների պատահական կարգ և էլեմենտների զանգվածի մեջտեղից հենակետային էլեմենտների ընտրությունը պատահական է։ Պրակտիկայում արագ տեսակավորումը ավելի արագ է, քան մնացած ալգորիթմները O(n lg n), այն պատճառով, որ ալգորիթմի ներքին ցիկլը կարող է ցանկացած շինարարության մեջ կիրառվել։ 2C_N/2 ծածկում է ստացված 2 զանգվածների տեսակավորման ծախսերը։ N- դա յուրաքանչյուր էլեմենտի վերամշակման գինն է։ Հայտնի է, որ այդ արտահայտությունը հավասար է C_N = N lg N.ь։
Վատթարագույն դեպք Վատթարագույն դեպքը կլինի այսպիսին, որի դեպքում յուրաքանչյուր էտապում զանգվածը հենակետային էլեմենտից կբաժանվի մի նոր զանգվածի։ Այդպիսի բան կարող է տեղի ունենալ, եթե վերամշակվածներից յուրաքանչյուր էտապում հենակետային ընտրվի կամ ամենամեծ կամ ամենափոքր էլեմենտը։

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

Բարելավում

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

Առավելություններ և թերություններ

Առավելություններ

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

Թերություններ

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

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

↑ ^1,0 ^1,1 https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/analysis-of-quicksort
↑ Hoare C. A. R. Algorithm 64: Quicksort // Commun. ACM — [New York]: Association for Computing Machinery, 1961. — Vol. 4, Iss. 7. — P. 321. — ISSN 0001-0782; 1557-7317 — doi:10.1145/366622.366644
↑ Steven S. Skiena (2011 թ․ ապրիլի 27). The Algorithm Design Manual. Springer. էջ 129. ISBN 978-1-84800-069-8. Վերցված է 2012 թ. նոյեմբերի 27-ին.

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

[_245bb7c94dfb4251-1] 1,0 ^1,1 https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/analysis-of-quicksort

[_aeb7fafb9152f0e5-2] Hoare C. A. R. Algorithm 64: Quicksort // Commun. ACM — [New York]: Association for Computing Machinery, 1961. — Vol. 4, Iss. 7. — P. 321. — ISSN 0001-0782; 1557-7317 — doi:10.1145/366622.366644

[3] Steven S. Skiena (2011 թ․ ապրիլի 27). The Algorithm Design Manual. Springer. էջ 129. ISBN 978-1-84800-069-8. Վերցված է 2012 թ. նոյեմբերի 27-ին.

[1]

[2]

[3]