Hipsort — разлика између измена
Садржај обрисан Садржај додат
м izvori; козметичке измене |
|||
Ред 12:
== Formiranje Hip-a ==
[[Датотека:Max-Heap.svg|мини|десно|Primer hip-a]]
U vezi sa hipsortom obratićemo posebno pažnju na početni deo algoritma, formiranje [http://en.wikipedia.org/wiki/Heap_(data_structure) hipa].
veći ili jednak od ključeva njegovih sinova. Pretpostavlja se
da se hip predstavlja implicitno, njegovi elementi smešteni su u niz A
Ред 18:
* koren je smešten u A[0]
<br />
* sinovi čvora zapisanog u A[i] smešteni su u A[2i] i A[2i+1]
<br />
<pre>
Ред 40:
end
</pre>
<br />
== Pseudokod ==
[[Датотека:Sorting_heapsort_anim.gif|оквир|десно|Primer rada hipsort algoritma.<br />
'''Vremenska složenost(prosečna)''': <math>O(n\text{ }\log\text{ }n)</math><br />
'''Vremenska složenost(najgora)''':<br />
'''Prostorna složenost''':
Algoritam hipsort izvršava se na isti način kao i sortiranje izborom,
razlika je u upotrebljenoj strukturi podataka za smeštanje niza. Ovde ćemo implementirati metodu koja uklanja maksimum iz hipa. Najpre se
elementi niza preuređuju tako da čine hip,
Zamenom A[0] sa A[n] postiže se da A[n] sadrži najveći elemenat niza.
Zatim
Ред 60:
(O(log n) po zameni) plus složenost formiranja hipa. Jasno je da je hipsort
sortiranje u mestu.
<br /><br />
<pre>
Algoritam Hipsort(X; n);
Ред 110:
'''Induktivna hipoteza (odozdo nagore)'''
Sva stabla predstavljena nizom A[i + 1]; A[i + 2],..., A[n] zadovoljavaju uslov hipa.
Ред 127:
== Primer ==
Neka { 6, 5, 3, 1, 8, 7, 2, 4 } bude niz koji želimo da sortiramo od najmanjeg do najvećeg.
[[
'''1. Formiranje hipa(odozgo-nadole)'''
{| class="wikitable"
Ред 160:
|}
<br />
'''2. Sortiranje.'''
{| class="wikitable"
Ред 217:
|}
== Literatura ==
* {{Citation |first=Miodrag |last=Živković |title=Algoritmi | pages=96-101 |url = http://poincare.matf.bg.ac.rs/~ezivkovm/nastava/algoritmi.pdf}}
* {{Citation |first=J. W. J. |last=Williams |title=Algorithm 232 - Heapsort |year=1964 |journal=Communications of the ACM |volume=7 |issue=6 |pages=347–348 |doi= }}
Ред 229:
== Spoljašnje veze ==
* [http://www.sorting-algorithms.com/heap-sort -{Animated Sorting Algorithms: Heap Sort] –
* [http://olli.informatik.uni-oldenburg.de/heapsort_SALA/english/start.html -{Courseware on Heapsort from Univ. Oldenburg] - With text, animations and interactive exercises}-
* [http://www.nist.gov/dads/HTML/heapSort.html -{NIST's Dictionary of Algorithms and Data Structures: Heapsort}-]
[[Категорија:Семинарски радови/МАТФ април и мај 2013.]]
[[Категорија:
| |||