Hipsort — разлика између измена
Ред 44: | Ред 44: | ||
(O(log n) po zameni) plus složenost formiranja hipa. Jasno je da je hipsort |
(O(log n) po zameni) plus složenost formiranja hipa. Jasno je da je hipsort |
||
sortiranje u mestu. |
sortiranje u mestu. |
||
<pre>Algoritam Hipsort(X; n); |
<pre> |
||
Algoritam Hipsort(X; n); |
|||
Ulaz: X (niz od n brojeva). |
|||
Izlaz: X (sortirani niz). |
|||
begin |
begin |
||
Preurediti X tako da bude hip; fvideti nastavak tekstag |
Preurediti X tako da bude hip; fvideti nastavak tekstag |
||
for i := n downto 2 do |
for i := n downto 2 do |
||
zameni (X[1]; X [n]); |
zameni (X[1]; X [n]); |
||
Skini max sa hipa(i - 1) |
Skini max sa hipa(i - 1) |
||
end |
end |
||
Ред 58: | Ред 59: | ||
Ulaz: A (niz veličine n za smeštanje hipa). |
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). |
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" |
if n = 0 then print "hip je prazan" |
||
else |
else |
||
Ред 76: | Ред 77: | ||
else |
else |
||
Sin := n + 1 /*da bi se iskočilo iz petlje*/ |
Sin := n + 1 /*da bi se iskočilo iz petlje*/ |
||
end |
|||
Algoritam Upis u hip(A; n; x); |
Algoritam Upis u hip(A; n; x); |
||
Ulaz: A ( |
Ulaz: A (niz veličine n za smeštanje hipa), x (broj). |
||
Izlaz: A (novi hip), n (nova |
Izlaz: A (novi hip), n (nova veličina hipa). |
||
begin |
begin |
||
n := n + 1; /*pretpostavka je da novo n nije ve�će od veličine A*/ |
n := n + 1; /*pretpostavka je da novo n nije ve�će od veličine A*/ |
Верзија на датум 27. мај 2013. у 16:18
Овај чланак је део пројекта семинарских радова на Математичком факултету у Београду. Датум уноса: април—мај 2013. Ова група студената уређиваће у простору чланака. Немојте пребацивати чланак у друге именске просторе. Позивамо вас да допринесете његовом квалитету и помогнете студентима при уређивању. |
Hipsort (eng. Heapsort) je algoritam sortiranja koji sortira zadati niz(ili listu). Hipsort je još jedan primer brzog algoritma za sortiranje. U praksi on, za velike n, obično nije tako brz kao sortiranje razdvajanjem, ali nije ni mnogo sporiji. S druge strane, za razliku od sortiranja razdvajanjem, njegova efikasnost je garantovana. Kao kod sortiranja objedinjavanjem, složenost hipsorta u najgorem slucaju je O(n log n). Za razliku od sortiranja objedinjavanjem, hipsort je algoritam sortiranja u mestu.
Opis
Hipsort algoritam može da se podeli u dva dela.
U prvom delu algoritma, formira se hip od zadatih podataka(niza ili liste).
U drugom delu, pravi se sortirani niz od elemenata koja su uklonjena ih hipa. Kada se svi elementi uklone iz hipa, dobijen je sortiran niz. Rezultujući niz može biti sortiran u opadajućem ili u rastućem poretku, u zavisnosti od toga da li se uklanja maksimalan ili minimalan elemenat iz hipa.
Hipsort je algoritam koji radi u mestu. Niz se može podeliti u dva dela, u sortiran niz i hip.
Formiranje Hip-a
U vezi sa hipsortom obratićemo posebno pažnju na početni deo algoritma, formiranje hipa. Hip je binarno stablo koje zadovoljava uslov hipa: ključ svakog čvora je veći ili jednak od klju;eva njegovih sinova. Pretpostavlja se da se hip predstavlja implicitno, njegovi elementi smešteni su u niz A dužine n, koji stablu odgovara na sledeći način:
- koren je smešten u A[0]
- sinovi čvora zapisanog u A[i] smešteni su u A[2i] i A[2i+1]
Pseudokod
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, Ako je hip u nizu A, onda je A[0] najveći elemenat hipa. Zamenom A[0] sa A[n] postiže se da A[n] sadrži najveći elemenat niza. Zatim se razmatra niz A[0], A[1],...,A[n - 1]; preuređuje se, tako da i dalje zadovoljava uslov hipa (problem je jedino novi elemenat A[0]). Posle toga se sa tim nizom rekurzivno ponavlja postupak primenjen na niz A[0],A[1],..., A[n]. Sve u svemu, algoritam se sastoji od početnog formiranja hipa i n+1 koraka, u kojima se vrši po jedna zamena i preuređivanje hipa. Preuređivanje hipa je u osnovi isti postupak kao algoritam za uklanjanje najvećeg elementa iz hipa. Formiranje hipa je samo po sebi interesantan problem, pa će biti posebno razmatran. Vremenska složenost algoritma je dakle O(n log n) (O(log n) po zameni) plus složenost formiranja hipa. Jasno je da je hipsort sortiranje u mestu.
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 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 fza iskaka�e iz pet eg end
Reference
- Živković, Miodrag, Algoritmi, стр. 96—101