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

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