Վիքիպեդիա

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

Դիտել պատմությունը
← Նախորդ տարբՀաջորդ տարբ →
Content deleted Content added
ՎիզուալԵլատեքստ
No edit summary
չ կետադրություն և բացատներ, փոխարինվեց: ն։Կ → ն։ Կ (3) oգտվելով ԱՎԲ
Տող 1.
[[պատկեր:Sorting heapsort anim.gif|right|Անիմացված ալգորիթմի գծապատկեր]]
'''Կույտային դասակարգումը''' առաջարկվել է Ջ.Ուիլիամսի կողմից 1964 թվականին։Կույտայինթվականին։ Կույտային դասակարգումը (անգլերեն Heapsort) դասակարգման ալգորիթմ է, որը աշխատում է վատ, միջին և լավ դեպքերում (այսինքն երաշխավորված է) Θ(n log n) օպերացիաների համար n հատ էլեմենտ տեսակավորելիս։ Ծառայող հիշողության օգտագործվող քանակը կախված չէ զանգվածի չափերից (այսինքն` O(1)):
Կարող է դիտվել որպես պղպջակային դասակարգման կատարելագործում, որում տարրը լողում է (min-heap), սուզվում (max-heap) բազմազան ուղիներով։
 
Տող 20.
Այդ քայլը պահանջում է <math>O(n)</math> օպերացիաներ։
 
2. Արմատից պետք է ջնջել տարրերը մեկը մյուսի հետևից և վերակառուցել ծառը։Այսինքնծառը։ Այսինքն առաջին քայլում տեղափոխում ենք Array[1] ի Array[n]` ձևավորելով Array[1], Array[2], … , Array[n-1] դասակարգվող ծառը. Որից հետո վերադասավորում ենք Array[1] и Array[n-1], ձևավորում Array[1], Array[2], … , Array[n-2] դասակարգվող ծառում։.Պրոցեսը շարունակվում է այնքան ժամանակ մինչև դասակարգվող ծառում չի մնա ոչ մի տարր։ Այդ դեպքում Array[1], Array[2], … , Array[n] կարգավորող հաջորդականություն է։.
Այս քայլը պահանջում է O(nlogn) օպերացիաներ։
 
Տող 37.
''O''(''n'') հիշողության ծախսումը միաձուլման դասակարգման միջոցով ավելի արագ է (<math>O(n\cdot\log n)</math>)փոքր հաստատունով և հակված չէ անհաջող տվյալների պատճառով դեգրադացման :
 
Ալգորիթմի դժվարության պատճառով շահումը լինում է միայն մեծատառ ''n''-ով։Ոչով։ Ոչ մեծատառ ''n''-ի համար ավելի արագ է Շելլայի տեսակավորումը։]].
 
 
Ստացված է «https://hy.wikipedia.org/wiki/Կույտային_դասակարգում» էջից