«Արագ տեսակավորում»–ի խմբագրումների տարբերություն

* ընտրել հենակետային անվանումով էլեմենտ,

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

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

# Ընտրում ենք զանգվածից մի քանի էլեմենտ, որոնք պետք է անվանենք հենակետային էլեմենտ։ Ալգորիթմի կոռեկտության տեսանկյունից հենակետային էլեմենտի ընտրությունը անկարևոր է։ Ալգորիթմի էֆեկտիվության բարձրացման տեսանկյունից պետք է ընտրվի մեդիանան, բայց առանց լրացուցիչ տեսակավորված տվյալների հնարավոր չէ տեղեկություն ստանալ։ Հայտնի ստրատեգիա է՝ մշտապես ընտրել միևնույն էլեմենտը, օրինակ մեջտեղի կամ վերջին զետեղվածը, ընտրել պատահական ինդեքսով ընտրված էլեմենտ:էլեմենտ։

# Զանգվածից բաժանման օպերացիան՝ վերակազմել զանգվածը այնպես, որպեսզի բոլոր էլեմենտները փոքր կամ հավասար գտնվեն հենակետային էլեմենտից ձախ, իսկ հենակետայինից մեծը՝ նրանից աջ։ Օպերացիայի ալգորիթմն է՝

## Ինդեքս l-ին մեծանում է մինչև m-ը այնքան ժամանակ, քանի դեռ l էլեմենտը չի գերազանցել հենակետայինին:հենակետայինին։

## Ինդեքս r-ը փոքրանում է մինչև m-ը այնքան ժամանակ, քանի դեռ r էլեմենտը չի թվացել փոքր կամ հավասար հենակետայինին:հենակետայինին։

## Եթե r = l — գտնվում է զանգվածի մեջտեղում — բաժանման օպերացիան ավարտված է, 2 ինդեքսներն էլ ցույց են տալիս հենակետային էլեմենտը:էլեմենտը։

## Եթե 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''&nbsp;lg&nbsp;''n'') կարգավորված ''n'' էլեմենտների փոխանակում:փոխանակում։ Իրականում հենց այդպիսի իրավիճակը ունենում է էլեմենտների պատահական կարգ և էլեմենտների զանգվածի մեջտեղից հենակետային էլեմենտների ընտրությունը պատահական է:է։ Պրակտիկայում արագ տեսակավորումը ավելի արագ է, քան մնացած ալգորիթմները O(''n''&nbsp;lg&nbsp;''n''), այն պատճառով, որ ալգորիթմի ներքին ցիկլը կարող է ցանկացած շինարարության մեջ կիրառվել:կիրառվել։ 2C_N/2 ծածկում է ստացված 2 զանգվածների տեսակավորման ծախսերը:ծախսերը։ N- դա յուրաքանչյուր էլեմենտի վերամշակման գինն է:է։ Հայտնի է, որ այդ արտահայտությունը հավասար է C_N = N lg N.ь:

* '''Վատթարագույն դեպք''' Վատթարագույն դեպքը կլինի այսպիսին, որի դեպքում յուրաքանչյուր էտապում զանգվածը հենակետային էլեմենտից կբաժանվի մի նոր զանգվածի:զանգվածի։ Այդպիսի բան կարող է տեղի ունենալ, եթե վերամշակվածներից յուրաքանչյուր էտապում հենակետային ընտրվի կամ ամենամեծ կամ ամենափոքր էլեմենտը։

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

* Ընտրել միջինը հենակետային 3 էլեմենտ (առաջին, միջին և վերջին):։ Այսպիսի ընտրությունը ուղղված է վատ պատահարի դեմ:դեմ։

* Բաժանել զանգվածը ոչ թե 2, այլ 3 մասի:մասի։ (տես [http://iaroslavski.narod.ru/quicksort/index.html Dual Pivot Quicksort]).

* Պարզ է իրականացման մեջ:մեջ։

* Ընդամենը պահանջում է <math>O(\lg n)</math> լրացուցիչ հիշողություն իր աշխատանքի համար:համար։

* Գոյություն ունի տողերի տեսակավորման էֆեկտիվ վերափոխություն ([[Սեդժվիկի ալգորիթմ]]) — սկզբում համեմատել հենակետային էլեմենտը զրոյական սիմվոլի տողի հետ, այնուհետև կիրառել անալոգային տեսակավորման համար «մեծ» և «փոքր» զանգվածներ, որոնք նույնպես համեմատել զրոյականի հետ, իսկ «հավասար» զանգվածը արդեն առաջին սիմվոլի հետ:հետ։

* Ուժեղ վատթարանում է արագությունը (մինչև <math>\Theta(n^2)</math>) հենակետային էլեմենտների անհաջող ընտրության ժամանակ, որը կարող է տեղի ունենալ անհաջող ելքային տվյալների մուտքագրման ժամանակ։ Դրանից կարելի է խուսափել՝ օգտագործելով այնպիսի վերափոխություն, ինչպիսին [[Introsort]] կամ հավանական է ընտրել պատահական հենակետային էլեմենտ, բայց ոչ ֆիքսված եղանակով:եղանակով։

* Ալգորիթմի իրականացումը կարող է բերել ստեկի գերհագեցման սխալի, այնպես ինչպես նրան կարող է անհրաժեշտ լինի կատարել <math>O(n)</math> ռեկուրսիվ ներդրման կանչեր:կանչեր։ Բարելավված իրականացումը, որում ռեկուրսիվ կանչերը տեղի են ունենում 2 զանգվածներից փոքրի տեսակավորման համար, ռեկուրսիայի խորությունը չի գերազանցում <math>O(\lg n)</math>:

* [[Կայուն]] — եթե պահանջվում է կայունություն` պետք է ընդլայնել բանալին:բանալին։