Heapsort

Վիքիպեդիայից՝ ազատ հանրագիտարանից

Կույտային դասակարգումը առաջարկվել է Ջ.Ուիլիամսի կողմից 1964 թվականին:Կույտային դասակարգումը (անգլերեն Heapsort) դասակարգման ալգորիթմ է, որը աշխատում է վատ, միջին և լավ դեպքերում (այսինքն երաշխավորված է) Θ(n log n) օպերացիաների համար n հատ էլեմենտ տեսակավորելիս: Ծառայող հիշողության օգտագործվող քանակը կախված չէ զանգվածի չափերից (այսինքն` O(1)): Կարող է դիտվել որպես պղպջակային դասակարգման կատարելագործում, որում տարրը լողում է (min-heap), սուզվում (max-heap) բազմազան ուղիներով: Անիմացված ալգորիթմի գծապատկեր


Ալգորիթմ[խմբագրել]

Կույտային դասակարգումը օգտագործում է դասակարգող ծառը: Դա այն բինար ծառն է, որը կատարում է հետևյալ պայմանները.

  1. Ամեն ճյուղ ունի կամ d, կամ (d − 1) երկարություն, որտեղ d` ծառի առավելագույն երկարությունն է:
  2. Ցանկացած գագաթի արժեք մեծ է իր հաջորդից:

Դասակարգվող ծառի համար հարմար տվյալների կառուցվածքը այնպիսի Array զանգված է, որտեղ Array[1] արմատային տարր է, իսկ Array[i]-ի հաջորդողները Array[2i] և Array[2i+1]-ն են: Դասակարգման ալգորիթմը բաղկացած է 2 հիմնական քայլերից:

1. Դասավորում ենք զանգվածի տարրերը դասակարգվող ծառի տեսքով:

Array[i]\geq Array[2i]

Array[i]\geq Array[2i+1]

երբ 1\leq i<n/2.

Այդ քայլը պահանջում է O(n) օպերացիաներ:

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) օպերացիաներ:

Առավելությունները և թերությունները[խմբագրել]

Առավելություն.

  • ունի ապացուցված գնահատական վատ դեպքի համար O(n \log n).
  • պահանջում է ընդամենը O(1) լրացուցիչ հիշողություն (եթե ծառը կազմակերպենք այնպես, ինչպես վերևում է ցույց տրված):

Թերություններ.

  • դժվար է իրականացվում,
  • անկայուն է `կայունության ապահովման համար պետք է ընդլայնել բանալին,
  • գրեթե տեսակավորված զանգվածում աշխատում է այնքան ժամանակ, որքան քաոսային տվյալների վրա,
  • ընտրությունը ստիպված պետք է անել քաոսային ձևով զանգվածի ամբողջ երկարությամբ, այդ իսկ պատճառով ալգորիթմը վատ է զուգորդվում քեշավորված և ներմղված հիշողության հետ:

O(n) հիշողության ծախսումը միաձուլման դասակարգման միջոցով ավելի արագ է (O(n\cdot\log n))փոքր հաստատունով և հակված չէ անհաջող տվյալների պատճառով դեգրադացման :

Ալգորիթմի դժվարության պատճառով շահումը լինում է միայն մեծատառ n-ով:Ոչ մեծատառ n-ի համար ավելի արագ է Շելլայի տեսակավորումը:]].


Գրականություն[խմբագրել]

Հղումներ[խմբագրել]

Կաղապար:Алгоритмы сортировки Категория:Алгоритмы сортировки