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

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

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

• ընտրել հենակետային անվանումով էլեմենտ,
• համեմատել մնացած էլեմենտները հենակետայինի հետ, համեմատման հիման վրա բաժանել քանակությունը 3 մասի - «փոքր հենակետային», «հավասար» և«մեծ», դասավորել նրանց հերթականությամբ՝ փոքր-հավասար-մեծ։
• կրկնել այն փոքրերի և մեծերի համար

Ալգորիթմ

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

1. Ընտրում ենք զանգվածից մի քանի էլեմենտ, որոնք պետք է անվանենք հենակետային էլեմենտ։ Ալգորիթմի կոռեկտության տեսանկյունից հենակետային էլեմենտի ընտրությունը անկարևոր է։ Ալգորիթմի էֆեկտիվության բարձրացման տեսանկյունից պետք է ընտրվի մեդիանան, բայց առանց լրացուցիչ տեսակավորված տվյալների հնարավոր չէ տեղեկություն ստանալ։ Հայտնի ստրատեգիա է՝ մշտապես ընտրել միևնույն էլեմենտը, օրինակ մեջտեղի կամ վերջին զետեղվածը, ընտրել պատահական ինդեքսով ընտրված էլեմենտ:
2. Զանգվածից բաժանման օպերացիան՝ վերակազմել զանգվածը այնպես, որպեսզի բոլոր էլեմենտները փոքր կամ հավասար գտնվեն հենակետային էլեմենտից ձախ, իսկ հենակետայինից մեծը՝ նրանից աջ։ Օպերացիայի ալգորիթմն է՝
   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 էլեմենտի համապատասխանաբար։
3. Ռեկուրսիվ կարգավորում ենք զանգվածները հենակետային էլեմենտների աջ և ձախ կողմերում:
4. Ռեկուրսիայի բազան համարվում է հավաքածու, որը բաղկացած է մեկ կամ երկու էլեմենտներից: Առաջինը վերադառնում է նախնական դիրքի, իսկ երկրորդ` անհրաժեշտության դեպքում, տեսակավորումը հասնում է 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).

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

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

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

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

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

Հղումներ

• Տեսակավորման ալգորիթմների անիմացիոն համեմատում
• Визуализаторы: [1], [2], [3]