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

Content deleted Content added
չ թարգմանում եմ անգլերեն ամսանունները oգտվելով ԱՎԲ
չ փոխարինվեց: է , → է, (6) oգտվելով ԱՎԲ
Տող 2.
'''Արագ տեսակավորումը''' ({{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=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''-ը ներկայացնում է անմիջական փոփոխման միջոցով ալգորիթմի տեսակավորման զգալիորեն բարելավված տարբերակ ( դրա տարբերակներն են «Պղպջակային տեսակավորումը» և « Թափահարման տեսակավորումը») , որը հայտնի է նաև իր ցածր արդյունավետությամբ։ Հիմնական տարբերությնն այն է , որ առաջին հերթին արվում եմ ամենամեծ հեռավորությնների վերադասավորումները և յուրաքանչյուր անցումից հետո էլեմենտները բաժանվում են երկու ինքնուրույն խմբերի։ Հետաքրքիր է , որ ամենաանարդյունավետ անմիջական տեսակավորման մեթոդի բարելավման արդյունքում ստեղծվեց ամենաարդյունավետ բարելավված մեթոդը։
Ալգորիթմի ընդհանուր միտքը կայանում է հետևյալում՝
* Ընտրել մատրիցայի անդամներից հենակետայինը , որը կարող է լինել ցանկացած էլեմենտ։
* Համեմատել մյուս էլեմենտները հենակետայինի հետ և դրանք դասավորել մատրիցայում այնպես , որ մատրիցան բաժանվի երեք շարունակական , մեկը մյուսին հաջորդող հատվածների հենակետայինից փոքր, հավասար և մեծ։
* «Մեծ» և «Փոքր» հատվածների համար կատարել գործողությունների նույն հաջորդականությունները, եթե հատվածի երկարությունը մեծ է մեկից։
Գործնականում մատրիցան բաժանվում է ոչ թե երեք, այլ երկու հատվածների՝ « հենակետայինից փոքր», «մեծ և հավասար»։ Այսպիսի մոտեցումն առավել արդյունավետ է , քանզի պարզեցնում է ալգորիթմի առանձնացումը։
Հոարը ստեղծեց այս մեթոդը մեքենայական թարգմանության կիրառմամբ։ Բառարանը պահվում էր մագնիսական ժապավենի վրա և մշակվող տեքստի բառերի ճիշտ դասակարգումը թույլ էր տալիս ստանալ դրանց թարգմանությունները մեկ ժապավենի վրա։ Հոանը հնարեց այս ալգորիթմը Խորհրդային Միությունում մնալու ընթացքում, երբ Մոսկվայի համալսարանում սովորում էր համակարգչային թարգմանություն և զբաղվում էր ռուս- անգլերեն զրուցարանի ստեղծմամբ։