Արագ տեսակավորում (անգլ.՝ quicksort) հաճախ անվանում են qsort C լեզվի ստանդարտ գրադարանի իրականացման անունով։ Այն հայտնի դասակարգման ալգորիթմ է, որը մշակվել է անգլիացի ինֆորմատիկ Չարլզ Հոարի կողմից 1960 թվականին։ Զանգվածի տեսակավորման առաջին արագ ունիվերսալ ալգորիթմն է։ n հատ տարրերի տեսակավորման համար կատարում է միջինը O (n log n) համեմատություն։ Ամենավատ դեպքում կատարում է O(n2) համեմատություն, չնայած այսպիսի բան պատահում է հազվադեպ։ Quicksort-ը հաճախ ավելի արագ է գործում, քան այլ O(n log n) ալգորիթմները[3]։
Արագ տեսակավորում | |
---|---|
![]() Պատահական դասավորված արժեքների արագ տեսակավորման ալգորիթմի անիմացիոն տարբերակը։ Կարմիր ձողերը հենակետային տարրերն են. Անիմացիոն գործողության սկզբում որպես հենակետային է ընտրվել ամենաաջում գտնվող տարրը։ | |
Տեսակ | համեմատություններով դասակարգում, divide-and-conquer algorithm? և տեսակավորման ալգորիթմ |
Դաս | տեսակավորման ալգորիթմ |
Տվյալների կառուցվածք | |
Վատագույն դեպքում կատարումը | [1] |
Լավագույն դեպքում կատարումը | [1] |
Հայտնաբերող | Չարլզ Անտոնի Ռիչարդ Հոար[2] |
Ալգորիթմի հակիրճ նկարագրությունը
QuickSort-ը ներկայացնում է անմիջական փոփոխման միջոցով ալգորիթմի տեսակավորման զգալիորեն բարելավված տարբերակ ( դրա տարբերակներն են «Պղպջակային տեսակավորումը» և « Թափահարման տեսակավորումը») , որը հայտնի է նաև իր ցածր արդյունավետությամբ։ Հիմնական տարբերությնն այն է, որ առաջին հերթին արվում եմ ամենամեծ հեռավորությունների վերադասավորումները և յուրաքանչյուր անցումից հետո էլեմենտները բաժանվում են երկու ինքնուրույն խմբերի։ Հետաքրքիր է, որ ամենաանարդյունավետ անմիջական տեսակավորման մեթոդի բարելավման արդյունքում ստեղծվեց ամենաարդյունավետ բարելավված մեթոդը։
Ալգորիթմի ընդհանուր միտքը հետևյալում է՝
- Ընտրել մատրիցայի անդամներից հենակետայինը, որը կարող է լինել ցանկացած էլեմենտ։
- Համեմատել մյուս էլեմենտները հենակետայինի հետ և դրանք դասավորել մատրիցայում այնպես, որ մատրիցան բաժանվի երեք շարունակական, մեկը մյուսին հաջորդող հատվածների հենակետայինից փոքր, հավասար և մեծ։
- «Մեծ» և «Փոքր» հատվածների համար կատարել գործողությունների նույն հաջորդականությունները, եթե հատվածի երկարությունը մեծ է մեկից։
Գործնականում մատրիցան բաժանվում է ոչ թե երեք, այլ երկու հատվածների՝ « հենակետայինից փոքր», «մեծ և հավասար»։ Այսպիսի մոտեցումն առավել արդյունավետ է, քանզի պարզեցնում է ալգորիթմի առանձնացումը։ Հոարը ստեղծեց այս մեթոդը մեքենայական թարգմանության կիրառմամբ։ Բառարանը պահվում էր մագնիսական ժապավենի վրա և մշակվող տեքստի բառերի ճիշտ դասակարգումը թույլ էր տալիս ստանալ դրանց թարգմանությունները մեկ ժապավենի վրա։ Հոանը հնարեց այս ալգորիթմը Խորհրդային Միությունում մնալու ընթացքում, երբ Մոսկվայի համալսարանում սովորում էր համակարգչային թարգմանություն և զբաղվում էր ռուս- անգլերեն զրուցարանի ստեղծմամբ։
Ալգորիթմ
Արագ տեսակավորումը օգտագործում է «Բաժանիր և տիրիր» ստրատեգիան։ Ալգորիթմի քայլերի հաջորդականությունը հետևյալն է՝
- Ընտրում ենք զանգվածից մի քանի էլեմենտ, որոնք պետք է անվանենք հենակետային էլեմենտ։ Ալգորիթմի կոռեկտության տեսանկյունից հենակետային էլեմենտի ընտրությունը անկարևոր է։ Ալգորիթմի էֆեկտիվության բարձրացման տեսանկյունից պետք է ընտրվի մեդիանան, բայց առանց լրացուցիչ տեսակավորված տվյալների հնարավոր չէ տեղեկություն ստանալ։ Հայտնի ստրատեգիա է՝ մշտապես ընտրել միևնույն էլեմենտը, օրինակ մեջտեղի կամ վերջին զետեղվածը, ընտրել պատահական ինդեքսով ընտրված էլեմենտ։
- Զանգվածից բաժանման օպերացիան՝ վերակազմել զանգվածը այնպես, որպեսզի բոլոր էլեմենտները փոքր կամ հավասար գտնվեն հենակետային էլեմենտից ձախ, իսկ հենակետայինից մեծը՝ նրանից աջ։ Օպերացիայի ալգորիթմն է՝
- 2 ինդեքսներ - l և r, հավասարվում են բաժանվող զանգվածի մաքսիմալ և մինիմալ ինդեքսին։
- Առանձնացվում է ինդեքսի m հենակետային էլեմենտը։
- Ինդեքս l-ին մեծանում է մինչև m-ը այնքան ժամանակ, քանի դեռ l էլեմենտը չի գերազանցել հենակետայինին։
- Ինդեքս r-ը փոքրանում է մինչև m-ը այնքան ժամանակ, քանի դեռ r էլեմենտը չի թվացել փոքր կամ հավասար հենակետայինին։
- Եթե r = l - գտնվում է զանգվածի մեջտեղում - բաժանման օպերացիան ավարտված է, 2 ինդեքսներն էլ ցույց են տալիս հենակետային էլեմենտը։
- Եթե l < r - գտնված զույգ էլեմենտները հարկավոր է փոխել տեղերով և շարունակել բաժանման օպերացիան մինչև l և r հասանելի լինեն։ Հարկավոր է հաշվել, որ եթե ինչ-որ սահման (l կամ r) հասել է մինչև հենակետային էլեմենտի, ապա m-ի փոխանակության իմաստը փոխվում է r կամ l էլեմենտի համապատասխանաբար։
- Ռեկուրսիվ կարգավորում ենք զանգվածները հենակետային էլեմենտների աջ և ձախ կողմերում։
- Ռեկուրսիայի բազան համարվում է հավաքածու, որը բաղկացած է մեկ կամ երկու էլեմենտներից։ Առաջինը վերադառնում է նախնական դիրքի, իսկ երկրորդ՝ անհրաժեշտության դեպքում, տեսակավորումը հասնում է 2 էլեմենտների վերադասավորմանը։
Հետաքրքիր է, որ Խոարը մշակել է այս մեթոդը մեքենայական թարգմանության կիրառմամբ։ Բանն այն է, որ այդ ժամանակ բառարանը պահվում էր մագնիսական ժապավենի վրա, և եթե կարգավորել տեքստի բոլոր բառերը՝ նրա թարգմանությունը կարելի էր ստանալ 1 լրիվ ժապավենի վրա։
Էֆեկտիվության գնահատական
QuickSort հանդիսանում է գոյություն ունեցող տեսակավորման ալգորիթմի կատարելագործված տարբերակ ուղիղ փոխանակության օգնությամբ (նրա տարբերակները հայտնի են ինչպես«Պղպջակային տեսակավորում», այդ թվում հայտնի է նաև իր ցածր էֆեկտիվությամբ։ Սկզբունքային տարբերությունն այն է, որ յուրաքանչյուր անցումից հետո էլեմենտները բաժանվում են 2 անկախ խմբերի։
- Լավագույն դեպք Այդ ալգորիթմի համար լավագույն դեպքը, եթե յուրաքանչյուր կրկնապատկման ժամանակ յուրաքանչյուր զանգված բաժանվում է 2 հավասարամեծ զանգվածների։ Արագ տեսակավորման համեմատման արդյունքում հավասար կլինի ռեկուրսիվ արտահայտության իմաստին CN = 2CN/2+N, որի արտահայտության բացահայտ օրինակ է N lg N հավասարւմը։ Դա կտա տեսակավորման ավելի քիչ ժամանակ։
- Միջին Տալիս է միջինը O(n lg n) կարգավորված n էլեմենտների փոխանակում։ Իրականում հենց այդպիսի իրավիճակը ունենում է էլեմենտների պատահական կարգ և էլեմենտների զանգվածի մեջտեղից հենակետային էլեմենտների ընտրությունը պատահական է։ Պրակտիկայում արագ տեսակավորումը ավելի արագ է, քան մնացած ալգորիթմները O(n lg n), այն պատճառով, որ ալգորիթմի ներքին ցիկլը կարող է ցանկացած շինարարության մեջ կիրառվել։ 2CN/2 ծածկում է ստացված 2 զանգվածների տեսակավորման ծախսերը։ N- դա յուրաքանչյուր էլեմենտի վերամշակման գինն է։ Հայտնի է, որ այդ արտահայտությունը հավասար է CN = N lg N.ь։
- Վատթարագույն դեպք Վատթարագույն դեպքը կլինի այսպիսին, որի դեպքում յուրաքանչյուր էտապում զանգվածը հենակետային էլեմենտից կբաժանվի մի նոր զանգվածի։ Այդպիսի բան կարող է տեղի ունենալ, եթե վերամշակվածներից յուրաքանչյուր էտապում հենակետային ընտրվի կամ ամենամեծ կամ ամենափոքր էլեմենտը։
Վատ դեպք տալիս է O(n²) փոխանակումը։ Բայց փոխանակման քանակը և համապատասխանաբար աշխատանքի ժամանակը նրա ոչ մեծ թերությունն է։ Վատը այն է, որ այդ դեպքում ռեկուրսիայի խորությունը ալգորիթմի կատարման ժամանակ հասնում է n, որը կնշանակի n համառոտակի հետադարձ հասցեի պահպանում։ Լայն իմաստով n վատ դեպքը կարող է բերել հիշողության փչացման ալգորիթմի աշխատանքի ժամանակ։
Բարելավում
- Տվյալ դիապազոնից հենակետային էլեմենտի ընտրության ժամանակ պատահական կերպով վատ դեպքը շատ քիչ հավանական է դառնում և ալգորիթմի տեսակավորման կատարման սպասված ժամանակը կլինի - O(n lg n).
- Ընտրել միջինը հենակետային 3 էլեմենտ (առաջին, միջին և վերջին)։ Այսպիսի ընտրությունը ուղղված է վատ պատահարի դեմ։
- Բաժանել զանգվածը ոչ թե 2, այլ 3 մասի։ (տես Dual Pivot Quicksort Արխիվացված 2015-02-02 Wayback Machine).
Առավելություններ և թերություններ
Առավելություններ
- Ամենաարագագործ ալգորիթմներից մեկը ներքին տեսակավորման ընդհանուր (պրակտիկայում) նշանակության
- Պարզ է իրականացման մեջ։
- Ընդամենը պահանջում է լրացուցիչ հիշողություն իր աշխատանքի համար։
- Հեշտ է համադրվում մեխանիզմների հետ քեշ հիշողություն և վերտուալ հիշողություն.
- Գոյություն ունի տողերի տեսակավորման էֆեկտիվ վերափոխություն (Սեդժվիկի ալգորիթմ) - սկզբում համեմատել հենակետային էլեմենտը զրոյական սիմվոլի տողի հետ, այնուհետև կիրառել անալոգային տեսակավորման համար «մեծ» և «փոքր» զանգվածներ, որոնք նույնպես համեմատել զրոյականի հետ, իսկ «հավասար» զանգվածը արդեն առաջին սիմվոլի հետ։
Թերություններ
- Ուժեղ վատթարանում է արագությունը (մինչև ) հենակետային էլեմենտների անհաջող ընտրության ժամանակ, որը կարող է տեղի ունենալ անհաջող ելքային տվյալների մուտքագրման ժամանակ։ Դրանից կարելի է խուսափել՝ օգտագործելով այնպիսի վերափոխություն, ինչպիսին Introsort կամ հավանական է ընտրել պատահական հենակետային էլեմենտ, բայց ոչ ֆիքսված եղանակով։
- Ալգորիթմի իրականացումը կարող է բերել ստեկի գերհագեցման սխալի, այնպես ինչպես նրան կարող է անհրաժեշտ լինի կատարել ռեկուրսիվ ներդրման կանչեր։ Բարելավված իրականացումը, որում ռեկուրսիվ կանչերը տեղի են ունենում 2 զանգվածներից փոքրի տեսակավորման համար, ռեկուրսիայի խորությունը չի գերազանցում ։
- Կայուն - եթե պահանջվում է կայունություն՝ պետք է ընդլայնել բանալին։
Ծանոթագրություններ
Արտաքին հղումներ
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.