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

Content deleted Content added
չ ուղղումներ ԱՎԶ ծրագրով
No edit summary
Տող 2.
 
== Ալգորիթմի հակիրճ նկարագրություն ==
* ընտրել էլեմենտ, հենակետային անվանումով
 
* համեմատել մնացած էլեմենտները հենակետայինի հետ , համեմատման հիման վրա բաժանել քանակությունը 3 մասի — «փոքր հենակետային», «հավասար» և«մեծ», դասավորել նրանց հեր-թականությամբ ` փոքր-հավասար-մեծ:
* ընտրել էլեմենտ, հենակետային անվանումով
* կրկնել այն փոքրերի և մեծերի համար
* համեմատել մնացած էլեմենտները հենակետայինի հետ , համեմատման հիման վրա բաժանել քանակությունը 3 մասի — «փոքր հենակետային», «հավասար» և«մեծ», դասավորել նրանց հեր-
թականությամբ ` փոքր-հավասար-մեծ:
* կրկնել այն փոքրերի և մեծերի համար
 
==Ալգորիթմ ==
Տող 21 ⟶ 19՝
#Ռեկուրսիայի բազան համարվում է հավաքածու, որը բաղկացած է մեկ կամ երկու էլեմենտներից: Առաջինը վեւադառնում է նախնական դիրքի, իսկ երկրորդ `անհրաժեշտության դեպքում, տեսակավորումը հասնում է 2 էլեմենտների վերադասավորմանը:
Հետաքրքիրէ, որ Խոարը մշակել է այս մեթոդը [[մեքենայական թարգմանության]] կիրառմամբ: Բանն այն է, որ այդ ժամանակ բառարանը պահվում էր [[մագնիսական ժապավենի]] վրա, և եթե կարգավորել տեքստի բոլոր բառերը` նրա թարգմանությունը կարելի էր ստանալ 1 լրիվ ժապավենի վրա:
 
==Էֆեկտիվության գնահատական==
QuickSort հանդիսանում է գոյություն ունեցող տեսակավորման ալգորիթմի կատարելագործված տարբերակ ուղիղ փոխանակության օգնությամբ(նրա տարբերակները հայտնի են ինչպես«[[Պղպջակային տեսակավորում]]», այդ թվում հայտնի է նաև իր ցածր էֆեկտիվությամբ:Սկզբունքային տարբերությունը կայանում է նրանում, որ յուրաքանչյուր անցումից հետո էլեմենտները բաժանվում են 2 անկախ խմբերի:
Տող 26 ⟶ 25՝
* '''Միջին.''' Տալիս է միջինը 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.ь:
* '''Վատթարագույն դեպք.''' Վատթարագույն դեպքը կլինի այսպիսին, որի դեպքում յուրաքանչյուր էտապում զանգվածը հենակետային էլեմենտից կբաժանվի մի նոր զանգվածի: Այդպիսի բան կարող է տեղի ունենալ, եթե վերամշակվածներից յուրաքանչյուր էտապում հենակետային ընտրվի կամ ամենամեծ կամ ամենափոքր էլեմենտը: <br /> Վատ դեպք տալիս է O(''n''²) փոխանակումը: Բայց փոխանակման քանակը և համապատասխանաբար աշխատանքի ժամանակը նրա ոչ մեծ թերությունն է:Վատը այն է, որ այդ դեպքում ռեկուրսիայի խորությունը ալգորիթմի կատարման ժամանակ հասնում է n, որը կնշանակի n համառոտակի հետադարձ հասցեի պահպանում: Լայն իմաստով n վատ դեպքը կարող է բերել հիշողության փչացման ալգորիթմի աշխատանքի ժամանակ:
 
== Բարելլավում ==
* Տվյալ դիապազոնից հենակետային էլեմենտի ընտրության ժամանակ պատահական կերպով վատ դեպքը շատ քիչ հավանական է դառնում և ալգորիթմի տեսակավորման կատարման սպասված ժամանակը կլինի - O(''n''&nbsp;lg&nbsp;''n'').
* Ընտրել միջինը հենակետային 3 էլեմենտ (առաջին, միջին և վերջին):Այսպիսի ընտրությունը ուղղված է վատ պատահարի դեմ:
* Բաժանել զանգվածը ոչ թե 2, այլ 3 մասի: (տես [http://iaroslavski.narod.ru/quicksort/index.html Dual Pivot Quicksort]).
 
== Առավելություններ և թերություններ ==
Առավելություններ
Տող 41 ⟶ 42՝
* Ալգորիթմի իրականացումը կարող է բերել ստեկի գերհագեցման սխալի, այնպես ինչպես նրան կարող է անհրաժեշտ լինի կատարել <math>O(n)</math> ռեկուրսիվ ներդրման կանչեր: Բարելավված իրականացումը, որում ռեկուրսիվ կանչերը տեղի են ունենում 2 զանգվածներից փոքրի տեսակավորման համար, ռեկուրսիայի խորությունը չի գերազանցում <math>O(\lg n)</math>:
* [[Կայուն]] —եթե պահանջվում է կայունություն` պետք է ընդլայնել բանալին:
== Ներածություն ==
 
== Ծանոթագրություններ ==
{{примечания}}
{{ծանցանկ}}
 
<!--== Գրականություն==
* {{книга
|часть = '''Глава 4. Метод декомпозиции: Быстрая сортировка'''
Տող 58 ⟶ 59՝
|издательство = [[Вильямс (издательство)|«Вильямс»]]
}}
* {{Книга:CLRS|2005|часть = '''Глава 7. Быстрая сортировка'''|страницы = 198-219}}-->
 
== Հղումներ ==
<!--{{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]