«Արագ տեսակավորում»–ի խմբագրումների տարբերություն
Content deleted Content added
չ թարգմանում եմ անգլերեն ամսանունները oգտվելով ԱՎԲ |
չ փոխարինվեց: է , → է, (6) oգտվելով ԱՎԲ |
||
Տող 2.
'''Արագ տեսակավորումը''' ({{lang-en|quicksort}}), հաճախ անվանում են qsort C լեզվի ստանդարտ գրադարանի իրականացման անունով։ Այն հայտնի դասակարգման [[ալգորիթմ]] է, որը մշակվել է անգլիացի ինֆորմատիկ [[Չարլզ Անտոնի Ռիչարդ Հոար|Չարլզ Հոարի]] կողմից 1960 թվականին։ Զանգվածի տեսակավորման առաջին արագ ունիվերսալ ալգորիթմն է։ ''n'' հատ տարրերի տեսակավորման համար կատարում է միջինը O(''n'' log ''n'') համեմատություն։ Ամենավատ դեպքում կատարում է O(''n''<sup>2</sup>) համեմատություն, չնայած այսպիսի բան պատահում է հազվադեպ։ Quicksort-ը հաճախ ավելի արագ է գործում, քան այլ O(''n'' log ''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''-ը ներկայացնում է անմիջական փոփոխման միջոցով ալգորիթմի տեսակավորման զգալիորեն բարելավված տարբերակ ( դրա տարբերակներն են «Պղպջակային տեսակավորումը» և « Թափահարման տեսակավորումը») , որը հայտնի է նաև իր ցածր արդյունավետությամբ։ Հիմնական տարբերությնն այն է
Ալգորիթմի ընդհանուր միտքը կայանում է հետևյալում՝
* Ընտրել մատրիցայի անդամներից հենակետայինը
* Համեմատել մյուս էլեմենտները հենակետայինի հետ և դրանք դասավորել մատրիցայում այնպես
* «Մեծ» և «Փոքր» հատվածների համար կատարել գործողությունների նույն հաջորդականությունները, եթե հատվածի երկարությունը մեծ է մեկից։
Գործնականում մատրիցան բաժանվում է ոչ թե երեք, այլ երկու հատվածների՝ « հենակետայինից փոքր», «մեծ և հավասար»։ Այսպիսի մոտեցումն առավել արդյունավետ է
Հոարը ստեղծեց այս մեթոդը մեքենայական թարգմանության կիրառմամբ։ Բառարանը պահվում էր մագնիսական ժապավենի վրա և մշակվող տեքստի բառերի ճիշտ դասակարգումը թույլ էր տալիս ստանալ դրանց թարգմանությունները մեկ ժապավենի վրա։ Հոանը հնարեց այս ալգորիթմը Խորհրդային Միությունում մնալու ընթացքում, երբ Մոսկվայի համալսարանում սովորում էր համակարգչային թարգմանություն և զբաղվում էր ռուս- անգլերեն զրուցարանի ստեղծմամբ։
|