Хипсорт
Хипсорт (енг. Хеапсорт) је алгоритам сортирања који сортира задати низ (или листу). Хипсорт је још један пример брзог алгоритма за сортирање. У пракси он, за велике н, обично није тако брз као сортирање раздвајањем, али није ни много спорији. С друге стране, за разлику од сортирања раздвајањем, његова ефикасност је гарантована. Као код сортирања обједињавањем, сложеност хипсорта у најгорем слуцају је О(н лог н). За разлику од сортирања обједињавањем, хипсорт је алгоритам сортирања у месту.
Опис уреди
Хипсорт алгоритам може да се подели у два дела.
У првом делу алгоритма, формира се хип од задатих података(низа или листе).
У другом делу, прави се сортирани низ од елемената који су уклоњени из хипа. Када се сви елементи уклоне из хипа, добијен је сортиран низ. Резултујући низ може бити сортиран у опадајућем или у растућем поретку, у зависности од тога да ли се уклања максималан или минималан елеменат из хипа.
Хипсорт је алгоритам који ради у месту. Низ се може поделити у два дела, у сортиран низ и хип.
Формирање Хип-а уреди
У вези са хипсортом обратићемо посебно пажњу на почетни део алгоритма, формирање хипа. Хип је бинарно стабло које задовољава услов хипа: кључ сваког чвора је већи или једнак од кључева његових синова. Претпоставља се да се хип представља имплицитно, његови елементи смештени су у низ А дужине н, који стаблу одговара на следећи начин:
- корен је смештен у А[1]
- синови чвора записаног у А[и] смештени су у А[2и] и А[2и+1]
Algoritam Upis u hip(A; n; x);
Ulaz: A (niz veličine n za smeštanje hipa), x (broj).
Izlaz: A (novi hip), n (nova veličina hipa).
begin
n := n + 1; /*pretpostavka je da novo n nije veće od veličine A*/
A[n] := x;
Sin := n;
Otac := n div 2;
while Otac >= 1 do
if A[Otac] < A[Sin] then
zameni (A[Otac]; A[Sin]);
Sin := Otac;
Otac := Otac div 2;
else
Otac := 0 /*za iskakanje iz petlje*/
end
Псеудокод уреди
Временска сложеност(просечна):
Временска сложеност(најгора):
Просторна сложеност:
Алгоритам хипсорт извршава се на исти начин као и сортирање избором,
разлика је у употребљеној структури података за смештање низа. Овде ћемо имплементирати методу која уклања максимум из хипа. Најпре се
елементи низа преуређују тако да чине хип, Ако је хип у низу А, онда је А[0] највећи елеменат хипа.
Заменом А[0] са А[н] постиже се да А[н] садржи највећи елеменат низа.
Затим
се разматра низ А[0], А[1],...,А[н - 1]; преуређује се, тако да и даље задовољава услов хипа (проблем је једино нови елеменат А[0]). После тога се са тим
низом рекурзивно понавља поступак примењен на низ А[0],А[1],..., А[н]. Све
у свему, алгоритам се састоји од почетног формирања хипа и н+1 корака,
у којима се врши по једна замена и преуређивање хипа. Преуређивање хипа
је у основи исти поступак као алгоритам за уклањање највећег елемента из
хипа. Временска сложеност алгоритма је дакле О(н лог н)
(О(лог н) по замени) плус сложеност формирања хипа. Јасно је да је хипсорт
сортирање у месту.
Algoritam Hipsort(X; n);
Ulaz: X (niz od n brojeva).
Izlaz: X (sortirani niz).
begin
Preurediti X tako da bude hip; fvideti nastavak tekstag
for i := n downto 2 do
zameni (X[1]; X [n]);
Skini max sa hipa(i - 1)
end
Algoritam Skini max sa hipa(A; n);
Ulaz: A (niz veličine n za smeštanje hipa).
Izlaz: Vrh hipa (najveći elemenat hipa), A (novi hip), n (nova veličina hipa; ako je n = 0 hip je prazan).
begin
if n = 0 then print "hip je prazan"
else
Vrh hipa := A[0];
A[0] := A[n];
n := n - 1;
Otac := 1;
if n > 1 then
Sin := 2;
while Sin <= n do
if Sin + 1 <= n and A[Sin] < A[Sin + 1] then
Sin := Sin + 1;
if A[Sin] > A[Otac] then
zameni (A[Otac]; A[Sin]);
Otac := Sin;
Sin := 2 * Sin;
else
Sin := n + 1 /*da bi se iskočilo iz petlje*/
end
Варијације формирања хипа уреди
Постоје два природна приступа формирању хипа: одозго-надоле и одоздо-нагоре. Они одговарају проласку кроз низ А удесно, односно здесна улево. Они ће бити представљени применом математичке индукције.
Индуктивна хипотеза (одозго надоле)
Низ А[0], А[1],..., А[и] представља хип.
Базни случај је тривијалан, јер А[0] јесте хип. Основни део алгоритма је
уградња елемента А[и + 1] у хип А[0], А[1],..., А[и]. Елемент А[и + 1] упоређује се са својим оцем, и замењује се са њим ако је већи од
њега. Нови елемент се премешта навише, све док не постане мањи или једнак
од оца, или док не доспе у корен хипа. Број упоређивања је у најгорем случају лог2(и+1).
Индуктивна хипотеза (одоздо нагоре)
Сва стабла представљена низом А[и + 1]; А[и + 2],..., А[н] задовољавају услов хипа. Индукција је по и, али обрнутим редоследом, и = н; н - 1,..., 1. Елемент А[н] очигледно представља хип, што представља базу индукције. Може се закључити и нешто више. Елементи вектора А са индексима од н/2+1 до н су листови стабла. Због тога се стабла која одговарају том низу састоје само од корена, па тривијално задовољавају услов хипа. Довољно је дакле да са индукцијом кренемо од и = н/2. То већ указује да би приступ одоздо нагоре могао бити ефикаснији, половина посла је тривијална, ово је још један пример важности пажљивог избора базе индукције. Размотримо сада елеменат А[и]. Он има највише два сина А[2и + 1] и А[2и], који су, према индуктивној хипотези, корени исправних хипова. Због тога је јасан начин укључивања А[и] у хип: А[и] се упоређује са већим од синова, и замењује се са њим ако је потребно. Са заменама се наставља наниже низ стабло, док претходна вредност елемента А[и] не дође до места на коме је већа од оба сина.
Пример уреди
Нека { 6, 5, 3, 1, 8, 7, 2, 4 } буде низ који желимо да сортирамо од најмањег до највећег.
1. Формирање хипа(одозго-надоле)
| Хип | нови елемент | замена елемената |
|---|---|---|
| нул | 6 | |
| 6 | 5 | |
| 6, 5 | 3 | |
| 6, 5, 3 | 1 | |
| 6, 5, 3, 1 | 8 | |
| 6, 5, 3, 1, 8 | 5, 8 | |
| 6, 8, 3, 1, 5 | 6, 8 | |
| 8, 6, 3, 1, 5 | 7 | |
| 8, 6, 3, 1, 5, 7 | 3, 7 | |
| 8, 6, 7, 1, 5, 3 | 2 | |
| 8, 6, 7, 1, 5, 3, 2 | 4 | |
| 8, 6, 7, 1, 5, 3, 2, 4 | 1, 4 | |
| 8, 6, 7, 4, 5, 3, 2, 1 |
2. Сортирање.
| Хип | замена елемената | брисање елемената | сортиран низ | кораци |
|---|---|---|---|---|
| 8, 6, 7, 4, 5, 3, 2, 1 | 8, 1 | замена 8 и 1 | ||
| 1, 6, 7, 4, 5, 3, 2, 8 | 8 | брисање 8 из хипа и убацивање у низ | ||
| 1, 6, 7, 4, 5, 3, 2 | 1, 7 | 8 | замена 1 и 7 јер нису у поретку правила хипа | |
| 7, 6, 1, 4, 5, 3, 2 | 1, 3 | 8 | замена 1 и 3 јер нису у поретку правила хипа | |
| 7, 6, 3, 4, 5, 1, 2 | 7, 2 | 8 | замена 7 и 2 за брисање 7 из хипа | |
| 2, 6, 3, 4, 5, 1, 7 | 7 | 8 | брисање 8 из хипа и убацивање у низ | |
| 2, 6, 3, 4, 5, 1 | 2, 6 | 7, 8 | замена 2 и 6 јер нису у поретку правила хипа | |
| 6, 2, 3, 4, 5, 1 | 2, 5 | 7, 8 | замена 2 и 5 јер нису у поретку правила хипа | |
| 6, 5, 3, 4, 2, 1 | 6, 1 | 7, 8 | замена 6 и 1 за брисање 6 из хипа | |
| 1, 5, 3, 4, 2, 6 | 6 | 7, 8 | брисање 6 из хипа и убацивање у низ | |
| 1, 5, 3, 4, 2 | 1, 5 | 6, 7, 8 | замена 1 и 5 јер нису у поретку правила хипа | |
| 5, 1, 3, 4, 2 | 1, 4 | 6, 7, 8 | замена 1 и 4 јер нису у поретку правила хипа | |
| 5, 4, 3, 1, 2 | 5, 2 | 6, 7, 8 | замена 5 и 2 за брисање 5 из хипа | |
| 2, 4, 3, 1, 5 | 5 | 6, 7, 8 | брисање 5 из хипа и убацивање у низ | |
| 2, 4, 3, 1 | 2, 4 | 5, 6, 7, 8 | замена 2 и 4 јер нису у поретку правила хипа | |
| 4, 2, 3, 1 | 4, 1 | 5, 6, 7, 8 | замена 4 и 1 за брисање 4 из хипа | |
| 1, 2, 3, 4 | 4 | 5, 6, 7, 8 | брисање 4 из хипа и убацивање у низ | |
| 1, 2, 3 | 1, 3 | 4, 5, 6, 7, 8 | замена 1 и 3 јер нису у поретку правила хипа | |
| 3, 2, 1 | 3, 1 | 4, 5, 6, 7, 8 | замена 3 и 1 за брисање 3 из хипа | |
| 1, 2, 3 | 3 | 4, 5, 6, 7, 8 | брисање 3 из хипа и убацивање у низ | |
| 1, 2 | 1, 2 | 3, 4, 5, 6, 7, 8 | замена 1 и 2 јер нису у поретку правила хипа | |
| 2, 1 | 2, 1 | 3, 4, 5, 6, 7, 8 | замена 2 и 1 за брисање 2 из хипа | |
| 1, 2 | 2 | 3, 4, 5, 6, 7, 8 | брисање 2 из хипа и убацивање у низ | |
| 1 | 1 | 2, 3, 4, 5, 6, 7, 8 | брисање 1 из хипа и убацивање у низ | |
| 1, 2, 3, 4, 5, 6, 7, 8 | крај |
Литература уреди
- Живковић, Миодраг, Алгоритми (ПДФ), стр. 96—101
- Wиллиамс, Ј. W. Ј. (1964), „Алгоритхм 232 - Хеапсорт”, Цоммуницатионс оф тхе АЦМ, 7 (6): 347—348
- Флоyд, Роберт W. (1964), „Алгоритхм 245 - Треесорт 3”, Цоммуницатионс оф тхе АЦМ, 7 (12): 701
- Царлссон, Сванте (1987), „Авераге-цасе ресултс он хеапсорт”, БИТ, 27 (1): 2—17
- Кнутх, Доналд (1997). „§5.2.3, Сортинг бy Селецтион”. Сортинг анд Сеарцхинг. Тхе Арт оф Цомпутер Программинг. 3 (тхирд изд.). Аддисон-Wеслеy. стр. 144—155. ИСБН 978-0-201-89685-5.
- Тхомас Х. Цормен, Цхарлес Е. Леисерсон, Роналд L. Ривест, анд Цлиффорд Стеин. Интродуцтион то Алгоритхмс, Сецонд Едитион. МИТ Пресс анд МцГраw-Хилл. 2001. ISBN 978-0-262-03293-3.. Chapters 6 and 7 Respectively: Heapsort and Priority Queues
- A PDF of Dijkstra's original paper on Smoothsort
- Heaps and Heapsort Tutorial by David Carlson, St. Vincent College
- Heaps of Knowledge
Спољашње везе уреди
- Courseware on Heapsort from Univ. Oldenburg - With text, animations and interactive exercises
- NIST's Dictionary of Algorithms and Data Structures: Heapsort
