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

[[Պատկեր:Sorting quicksort anim.gif|մինի|աջից|320px|Պատահական դասավորված արժեքների արագ տեսակավորման [[ալգորիթմ]]ի անիմացիոն տարբերակը։ Կարմիր ձողերը հենակետային տարրերն են. Անիմացիոն գործողության սկզբում որպես հենակետային է ընտրվել ամենաաջում գտնվող տարրը։]]

'''Արագ տեսակավորումը''' ({{lang-en|quicksort}}), հաճախ անվանում են qsort C լեզվի ստանդարտ գրադարանի իրականացման անունով։ Այն հայտնի դասակարգման [[ալգորիթմ]] է, որը մշակվել է անգլիացի ինֆորմատիկ [[Չարլզ Անտոնի Ռիչարդ Հոար|Չարլզ Հոարի]] կողմից 1960 թվականին։ Զանգվածի տեսակավորման առաջին արագ ունիվերսալ ալգորիթմն է։ ''n'' հատ տարրերի տեսակավորման համար կատարում է միջինը O(''n''&nbsp;log&nbsp;''n'') համեմատություն։ Ամենավատ դեպքում կատարում է O(''n''²) համեմատություն, չնայած այսպիսի բան պատահում է հազվադեպ։ Quicksort-ը հաճախ ավելի արագ է գործում, քան այլ O(''n''&nbsp;log&nbsp;''n'') ալգորիթմները։<ref>{{cite book|author=Steven S. Skiena|title=The Algorithm Design Manual|url=https://books.google.am/books?id=7XUSn0IKQEgC|accessdate=2012 թ․ նոյեմբերի 27|date=ապրիլի 27, 2011|publisher=Springer|isbn=978-1-84800-069-8|page=129}}</ref>

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

''QuickSort''-ը ներկայացնում է անմիջական փոփոխման միջոցով ալգորիթմի տեսակավորման զգալիորեն բարելավված տարբերակ ( դրա տարբերակներն են «Պղպջակային տեսակավորումը» և « Թափահարման տեսակավորումը») , որը հայտնի է նաև իր ցածր արդյունավետությամբ։ Հիմնական տարբերությնն այն է, որ առաջին հերթին արվում եմ ամենամեծ հեռավորությնների վերադասավորումները և յուրաքանչյուր անցումից հետո էլեմենտները բաժանվում են երկու ինքնուրույն խմբերի։ Հետաքրքիր է, որ ամենաանարդյունավետ անմիջական տեսակավորման մեթոդի բարելավման արդյունքում ստեղծվեց ամենաարդյունավետ բարելավված մեթոդը։

Հոարը ստեղծեց այս մեթոդը մեքենայական թարգմանության կիրառմամբ։ Բառարանը պահվում էր մագնիսական ժապավենի վրա և մշակվող տեքստի բառերի ճիշտ դասակարգումը թույլ էր տալիս ստանալ դրանց թարգմանությունները մեկ ժապավենի վրա։ Հոանը հնարեց այս ալգորիթմը Խորհրդային Միությունում մնալու ընթացքում, երբ Մոսկվայի համալսարանում սովորում էր համակարգչային թարգմանություն և զբաղվում էր ռուս- անգլերեն զրուցարանի ստեղծմամբ։

 

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

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

Հետաքրքիր է, որ Խոարը մշակել է այս մեթոդը [[մեքենայական թարգմանության]] կիրառմամբ։ Բանն այն է, որ այդ ժամանակ բառարանը պահվում էր [[մագնիսական ժապավենի]] վրա, և եթե կարգավորել տեքստի բոլոր բառերը՝ նրա թարգմանությունը կարելի էր ստանալ 1 լրիվ ժապավենի վրա։

 

QuickSort հանդիսանում է գոյություն ունեցող տեսակավորման ալգորիթմի կատարելագործված տարբերակ ուղիղ փոխանակության օգնությամբ (նրա տարբերակները հայտնի են ինչպես«[[Պղպջակային տեսակավորում]]», այդ թվում հայտնի է նաև իր ցածր էֆեկտիվությամբ։ Սկզբունքային տարբերությունը կայանում է նրանում, որ յուրաքանչյուր անցումից հետո էլեմենտները բաժանվում են 2 անկախ խմբերի։

* '''Լավագույն դեպք''' Այդ ալգորիթմի համար լավագույն դեպքը, եթե յուրաքանչյուր կրկնապատկման ժամանակ յուրաքանչյուր զանգված բաժանվում է 2 հավասարամեծ զանգվածների։ Արագ տեսակավորման համեմատման արդյունքում հավասար կլինի ռեկուրսիվ արտահայտության իմաստին C_N = 2C_N/2+N, որի արտահայտության բացահայտ օրինակ է N lg N հավասարւմը։ Դա կտա տեսակավորման ավելի քիչ ժամանակ։

 

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

* Ամենաարագագործ ալգորիթմներից մեկը ներքին տեսակավորման ընդհանուր (պրակտիկայում) նշանակության

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

== Ծանոթագրություններ ==

{{ծանցանկ}}

 

== Հղումներ ==

* [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]

 

[[Կատեգորիա:Դասակարգման ալգորիթմներ]]