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

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

Կարող է դիտվել որպես պղպջակային դասակարգման կատարելագործում, որում տարրը լողում է (min-heap), սուզվում (max-heap) բազմազան ուղիներով:ուղիներով։ [http://ru.wikipedia.org/w/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Sorting_heapsort_anim.gif&filetimestamp=20080103142112 Անիմացված ալգորիթմի գծապատկեր]

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

# Ամեն ճյուղ ունի կամ d, կամ (d − 1) երկարություն, որտեղ d` ծառի առավելագույն երկարությունն է:է։

# Ցանկացած գագաթի արժեք մեծ է իր հաջորդից:հաջորդից։

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

Դասակարգման ալգորիթմը բաղկացած է 2 հիմնական քայլերից:քայլերից։

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

Այդ քայլը պահանջում է <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) օպերացիաներ:օպերացիաներ։

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

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