Heapsort: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
k robot Erbij: he:מיון ערימה |
iteratief altenatief , andere presentatie, breder toepassingsgebied |
||
Regel 194:
}
</pre>
----
==== alternatief -- iteratief ====
===Sortering door middel van heaps===
De sorteermethode van heapsort is gebaseerd op een oplossing van:
# Maak uit elementen in willekeurige volgorde een rij van die elementen
# Produceer uit die rij van elementen deze elementen in de voorgeschreven volgorde
onder de voorwaarde: het toevoegen repectievelijk het verwijderen van een
element in 1 en 2 geschiedt in een tijd maximaal evenredig met de logaritme van het aantal
elementen in de rij.
gegeven:
de voorgeschreven volgorde 'geordend.(A,B)' is een [[ordening (wiskunde)|totale ordening]] en kan tussen willekeurige
elementen in vaste tijd worden geëvalueerd
De oplossing die hier gepresenteerd wordt is een rij met met elementen die voldoen aan:
<math>Heap.A=\langle\forall i,j : 2 \times i=j \vee 2 \times i+1=j : geordend.(A.i,A.j) \rangle </math>
of equivalent
<math>Heap.A=\langle\forall i :: geordend.(A.(i \mathbf{div} 2),A.i) \rangle </math>
===Het maken van een Heap uit elementen in willekeurige volgorde===
Men voege een nieuw element toe aan het eind van de rij die de heap bevat en confronteert het met het
element dat het in strijd met de voorwaarde zou kunnen brengen: A.(i DIV 2) , waar i zijn huidige positie is.
Als de heapvoorwaarde niet voldaan is verwisselen we de elementen. Dit wordt herhaald waarbij in elke slag
de index minstens halveert tot het nieuwe element de heapvoorwaarde niet meer verstoort.
Dit moet gebeuren omdat er geen lagere elementen meer zijn of het element index 0 krijgt.
Daar 0 DIV 2 = 0 en een totale ordening o.a. reflexief is geldt geordend(a,a).
Als we het onderste element van de heap index 0 heeft vereenvoudigt dit het programma:
{ vereist : Heap.A[0:n) }
{ vereist : A.lengte > n }
HeapIn ( var A : rij(elem), var n : integer, in : elem, geordend : (elem,elem)->Boolean)
|[ var i,j : integer;
{ n=N EN Heap.A[0:n) }
A.n:=in;
i,j,n:=n,n DIV 2,n+1;
do ¬geordend.(A.j,A.i) -> A:swap(i,j); i,j:=j,j DIV 2 od;
{ n=N+1 EN Heap.A[0:n) }
]|
NB. Heap.A[0:0) is triviaal geldig dus kan een Heap kan elementsgewijze met
HeapIn vanuit een lege Heap gemaakt worden.
===Het produceren van elementen uit een Heap in de voorgeschreven volgorde===
Het te leveren element is A.0.
Vervolgens moet de heap hersteld worden zodanig dat er een nieuwe A.0 is en de heap nu
aan het eind een element korter is.
Dit gebeurt door A.0 te vullen met A.1 en vervolgens de nieuwe vrije plek A.i te vullen met
het element uit {A.(2*i),A.(2*i+1)} dat het eerst voor promotie naar een lagere index in aanmerking komt.
We herhalen dit tot A(2*i+1) niet meer bestaat, waarbij de index van de vrije plek per slag minstens verdubbelt.
Wij vullen A.i nu met het laatste element in de rij, dat nu potentieel niet geordend is t.o.v. A.(i DIV 2).
Dit wordt op dezelfde wijze als bij het toevoegen van een nieuw element verholpen.
{ vereist : Heap.A[0:n) }
{ vereist : A.lengte >= n > 0 }
HeapUit (var A : rij(elem), var n : integer, var uit : elem, geordend : (elem,elem)->Boolean)
|[ var i,j :integer;
{ n=N+1 EN Heap.A[0:n) }
uit:= A.0;
A.0:=A.1;
i,j=1,2;
do j < n
-> if geordend.(A.j,A.(j+1)) -> A.i:=A.j; i,j:=j,2*j
[] geordend.(A.(j+1),A.j) -> A.i:=A.j+1;i,j:=j+1,2*(j+1)
fi
od;
j,n:=i DIV 2, n-1;
A.i:=A.n;
do ¬geordend.(A.j,A.i) -> A:swap(i,j); i,j:=j,j DIV 2 od;
{ n=N EN Heap.A[0:n) }
]|
Een groot voordeel van dit mechanisme is dat (bijna) de helft van het sorteren geschiedt
tijdens de invoerfase en de rest tijdens de uitvoerfase, en daarmee eventueel kan worden overlapt.
Dat bovendien de werkruimte-overhead O(1) (onafhankelijk van n) is, maakt de methode
aantrekkelijk voor het sorteren van hoeveelheden gegevens die de capaciteit van het snelle
random-access geheugen benadert of overstijgt.
Als dat laatste het geval is kunnen met de routine van een externe ongeordende rij maximaal
lange geordende externe subrijen worden geproduceerd, die vervolgens met behoud van ordening tot
langere subrijen worden samengevoegd tot de beschikbare geheugenruimte voldoende is om alle
resterende subrijen efficient tot de gewenste rij (op het externe medium) te combineren.
Ook is het een effectieve 'prioriteits-wachtrij' : als de activiteit met de hoogste prioriteit
de vroegste plaats in de ordening krijgt kan deze in log.n tijd geselecteerd worden. Een nieuwe
activiteit met willekeurige prioriteit kan in log.n tijd in de wachtrij worden gezet (waar n het
aantal wachtende activiteiten is).
Als een tabel met elementen in snel geheugen reeds bestaat en deze gesorteerd moet worden,
d.w.z er is een in-situ sorteerprocedure gewenst, kan dit gerealiseerd worden:
# Transformeer de Tabel van 0 tot Tabel.lengte in een heap doch met omgekeerde van de gewenste volgorde.
# Plaats de uit de heap geproduceerde elementen in de aan het eind vrijkomende plaatsen.
indien een oplopende ordening gewenst is:
HeapSort (var A : rij(elem))
|[ var n : integer;
aflopend(elem l,elem r)->Boolean |[ l>=r ]|;
{ aflopend.A = <Ai,j : i <= j : aflopend(A.i,A.j)> }
{ oplopend.A = <Ai,j : i <= j : aflopend(A.j,A.i)> }
n:=0;
{ Heap.A[0:n) }
do n < A.lengte -> HeapIn(A,n,A.n,aflopend) od;
{ n = A.lengte}
{ Heap.A[0:n) EN oplopend.A[n:A.lengte) }
do n > 0
-> |[var temp : elem;
HeapUit(A,n,temp,aflopend);
A.(n+1):=temp
]|
od
{ Heap.A[0:0) EN oplopend.A[0:A.lengte) }
]|
Het eerste deel van de slotconditie is geen kunst, het tweede was de opdracht.
[[Categorie:Sorteeralgoritme]]
Regel 213 ⟶ 342:
[[vi:Sắp xếp vun đống]]
[[zh:堆排序]]
--[[Gebruiker:J.Dering|J.Dering]] 29 aug 2007 09:32 (CEST)
| |||