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

Արագ տեսակավորումը (անգլերեն՝ 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)$:
• Կայուն —եթե պահանջվում է կայունություն` պետք է ընդլայնել բանալին:

Գրականություն

• Կաղապար:Книга
• Կաղապար:Книга:CLRS

Հղումներ

• Анимированное сравнение алгоритмов сортировки
• Визуализаторы: [1], [2], [3]