Կույտային դասակարգում

Կույտային դասակարգումը առաջարկվել է Ջ. Ուիլիամսի կողմից 1964 թվականին։ Կույտային դասակարգումը (Կաղապար:Lang-en) դասակարգման ալգորիթմ է, որն աշխատում է վատ, միջին և լավ դեպքերում (այսինքն երաշխավորված է) Θ(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]\ge Array[2i]$

$Array[i]\ge Array[2i+1]$

երբ $1\le 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-ի համար ավելի արագ է Շելլայի տեսակավորումը։]].

Գրականություն

• Կաղապար:Ռուսերեն գիրք
• Կաղապար:Книга:CLRS

Արտաքին հղումներ

• Пирамидальная сортировка Կաղապար:Webarchive — подробное описание с иллюстрациями и примером реализации на C++. Приведён вывод оценок скорости работы алгоритма и измерение времени работы на реальной вычислительной системе.
• Сортировка с помощью кучи (пирамидальная сортировка) Կաղապար:Webarchive — доходчивое описание с иллюстрациями и примером реализации на Pascal.