Վիքիպեդիա

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

Դիտել պատմությունը
← Նախորդ տարբՀաջորդ տարբ →
Content deleted Content added
ՎիզուալԵլատեքստ
No edit summary
չ clean up, փոխարինվեց: եւ → և (7), : → ։ (10), ` → ՝ (8), → (2) oգտվելով ԱՎԲ
Տող 1.
[[Պատկեր:Sorting quicksort anim.gif|մինի|աջից|320px|Պատահական դասավորված արժեքների արագ տեսակավորման [[ալգորիթմ]]ի անիմացիոն տարբերակը: Կարմիր ձողերը հենակետային տարրերն են. Անիմացիոն գործողության սկզբում որպես հենակետային է ընտրվել ամենաաջում գտնվող տարրը:]]
'''Արագ տեսակավորումը''' ({{lang-en|quicksort}}), հաճախ անվանում են qsort C լեզվի ստանդարտ գրադարանի իրականացման անունով։ Այն հայտնի դասակարգման [[ալգորիթմ]] է, որը մշակվել է անգլիացի ինֆորմատիկ [[Չարլզ Անտոնի Ռիչարդ Հոար|Չարլզ Հոարի]] կողմից 1960 թվականին։ Զանգվածի տեսակավորման առաջին արագ ունիվերսալ ալգորիթմն է:է։ ''n'' հատ տարրերի տեսակավորման համար կատարում է միջինը O(''n''&nbsp;log&nbsp;''n'') համեմատություն:համեմատություն։ Ամենավատ դեպքում կատարում է O(''n''<sup>2</sup>) համեմատություն, չնայած այսպիսի բան պատահում է հազվադեպ:հազվադեպ։ Quicksort-ը հաճախ ավելի արագ է գործում, քան այլ O(''n''&nbsp;log&nbsp;''n'') ալգորիթմները:ալգորիթմները։<ref>{{cite book|author=Steven S. Skiena|title=The Algorithm Design Manual|url=http://books.google.com/books?id=7XUSn0IKQEgC|accessdate=27 November 2012|date=27 April 2011|publisher=Springer|isbn=978-1-84800-069-8|page=129}}</ref>
== Ալգորիթմի հակիրճ նկարագրությունը ==
Արագ տեսակավորման ընդհանուր գաղափարը հետեւյալնհետևյալն է`է՝
* ամբողջ զանգվածից ընտրվում է մի որեւէ`որևէ՝ հենակետային տարր;
* մնացած բոլոր տարրերը համեմատվում են հենակետայինի հետ եւև, վերադասավորելով, բաժանվում են իրար հետեւողհետևող երեք մասերի`մասերի՝ «հենակետայինից փոքր», «հավասար» եւև «մեծ»;
* «ավելի փոքրերի» եւև «ավելի մեծերի» հատվածների համար կատարվում են գործողությունների նույն նույն հաջորդականությունները, եթե հատվածի երկարությունը մեծ է միավորից:միավորից։<br />
Գործնականում զանգվածը բաժանվում է ոչ թե երեք, այլ`այլ՝ երկու հատվածների, օրինակ`օրինակ՝ «հենակետայինից փոքրերի» եւև «հավասարների ու մեծերի»:։ Այդպիսի մոտեցումն ընդհանուր առմամբ առավել արդյունավետ է:է։
 
==Ալգորիթմ ==
Տող 19.
## Եթե l < r - գտնված զույգ էլեմենտները հարկավոր է փոխել տեղերով և շարունակել բաժանման օպերացիան միչև l և r հասանելի լինեն։ Հարկավոր է հաշվել, որ եթե ինչ-որ սահման (l կամ r)հասել է մինչև հենակետային էլեմենտի, ապա m-ի փոխանակության իմաստը փոխվում է r կամ l էլեմենտի համապատասխանաբար։
# [[Ռեկուրսիվ]] կարգավորում ենք զանգվածները հենակետային էլեմենտների աջ և ձախ կողմերում։
# Ռեկուրսիայի բազան համարվում է հավաքածու, որը բաղկացած է մեկ կամ երկու էլեմենտներից։ Առաջինը վերադառնում է նախնական դիրքի, իսկ երկրորդ`երկրորդ՝ անհրաժեշտության դեպքում, տեսակավորումը հասնում է 2 էլեմենտների վերադասավորմանը։
Հետաքրքիր է, որ Խոարը մշակել է այս մեթոդը [[մեքենայական թարգմանության]] կիրառմամբ։ Բանն այն է, որ այդ ժամանակ բառարանը պահվում էր [[մագնիսական ժապավենի]] վրա, և եթե կարգավորել տեքստի բոլոր բառերը`բառերը՝ նրա թարգմանությունը կարելի էր ստանալ 1 լրիվ ժապավենի վրա։
 
==Էֆեկտիվության գնահատական==
QuickSort հանդիսանում է գոյություն ունեցող տեսակավորման ալգորիթմի կատարելագործված տարբերակ ուղիղ փոխանակության օգնությամբ (նրա տարբերակները հայտնի են ինչպես«[[Պղպջակային տեսակավորում]]», այդ թվում հայտնի է նաև իր ցածր էֆեկտիվությամբ։ Սկզբունքային տարբերությունը կայանում է նրանում, որ յուրաքանչյուր անցումից հետո էլեմենտները բաժանվում են 2 անկախ խմբերի։
* '''Լավագույն դեպք''' Այդ ալգորիթմի համար լավագույն դեպքը, եթե յուրաքանչյուր կրկնապատկման ժամանակ յուրաքանչյուր զանգված բաժանվում է 2 հավասարամեծ զանգվածների։ Արագ տեսակավորման համեմատման արդյունքում հավասար կլինի ռեկուրսիվ արտահայտության իմաստին C<sub>N</sub> = 2C<sub>N/2</sub>+N, որի արտահայտության բացահայտ օրինակ է N lg N հավասարւմը։ Դա կտա տեսակավորման ավելի քիչ ժամանակ։
* '''Միջին''' Տալիս է միջինը O(''n''&nbsp;lg&nbsp;''n'') կարգավորված ''n'' էլեմենտների փոխանակում։ Իրականում հենց այդպիսի իրավիճակը ունենում է էլեմենտների պատահական կարգ և էլեմենտների զանգվածի մեջտեղից հենակետային էլեմենտների ընտրությունը պատահական է։ Պրակտիկայում արագ տեսակավորումը ավելի արագ է, քան մնացած ալգորիթմները O(''n''&nbsp;lg&nbsp;''n''), այն պատճառով, որ ալգորիթմի ներքին ցիկլը կարող է ցանկացած շինարարության մեջ կիրառվել։ 2C<sub>N/2</sub> ծածկում է ստացված 2 զանգվածների տեսակավորման ծախսերը։ N- դա յուրաքանչյուր էլեմենտի վերամշակման գինն է։ Հայտնի է, որ այդ արտահայտությունը հավասար է C<sub>N</sub> = N lg N.ь:ь։
* '''Վատթարագույն դեպք''' Վատթարագույն դեպքը կլինի այսպիսին, որի դեպքում յուրաքանչյուր էտապում զանգվածը հենակետային էլեմենտից կբաժանվի մի նոր զանգվածի։ Այդպիսի բան կարող է տեղի ունենալ, եթե վերամշակվածներից յուրաքանչյուր էտապում հենակետային ընտրվի կամ ամենամեծ կամ ամենափոքր էլեմենտը։
 
Տող 46.
===Թերություններ===
* Ուժեղ վատթարանում է արագությունը (մինչև <math>\Theta(n^2)</math>) հենակետային էլեմենտների անհաջող ընտրության ժամանակ, որը կարող է տեղի ունենալ անհաջող ելքային տվյալների մուտքագրման ժամանակ։ Դրանից կարելի է խուսափել՝ օգտագործելով այնպիսի վերափոխություն, ինչպիսին [[Introsort]] կամ հավանական է ընտրել պատահական հենակետային էլեմենտ, բայց ոչ ֆիքսված եղանակով։
* Ալգորիթմի իրականացումը կարող է բերել ստեկի գերհագեցման սխալի, այնպես ինչպես նրան կարող է անհրաժեշտ լինի կատարել <math>O(n)</math> ռեկուրսիվ ներդրման կանչեր։ Բարելավված իրականացումը, որում ռեկուրսիվ կանչերը տեղի են ունենում 2 զանգվածներից փոքրի տեսակավորման համար, ռեկուրսիայի խորությունը չի գերազանցում <math>O(\lg n)</math>:։
* [[Կայուն]] - եթե պահանջվում է կայունություն`կայունություն՝ պետք է ընդլայնել բանալին։
 
== Ծանոթագրություններ ==
Տող 70.
<!--{{wikibooks|Примеры реализации быстрой сортировки|Примеры реализации быстрой сортировки}}-->
* [http://www.sorting-algorithms.com/quick-sort Տեսակավորման ալգորիթմների անիմացիոն համեմատում]
* Визуализаторы:Визуализаторы։ [http://rain.ifmo.ru/cat/view.php/vis/sorts/quicksort-2004], [http://rain.ifmo.ru/cat/view.php/vis/sorts/quicksort-2000], [http://prototype-nk.ru/quicksort.html]
 
[[Կատեգորիա:Դասակարգման ալգորիթմներ]]
Ստացված է «https://hy.wikipedia.org/wiki/Արագ_տեսակավորում» էջից