Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- -module(heapsortCarl).
- -export([hsort/1]).
- % Kodierung des Feldes: Nachfolger von Position i ist 2*i links und 2*i+1 rechts
- % berechnet den Pfad zur ersten leeren Position
- % l steht fuer links, r fuer rechts
- % Beispiel: sort:calcPath(1). --> []
- % sort:calcPath(2). --> [l]
- % sort:calcPath(3). --> [r]
- % sort:calcPath(4). --> [l,l]
- % sort:calcPath(5). --> [l,r]
- % sort:calcPath(6). --> [r,l]
- % sort:calcPath(7). --> [r,r]
- calcPath(Number) -> calcPath(Number,[]).
- % aktuelle Position ist Wurzel
- calcPath(1,Accu) -> Accu;
- % aktuelle Position ist gerade
- calcPath(Number,Accu) when Number rem 2 =:= 0 -> calcPath(Number div 2,[l|Accu]);
- % aktuelle Position ist ungerade
- calcPath(Number,Accu) when Number rem 2 =/= 0 -> calcPath((Number-1) div 2,[r|Accu]).
- hsort(Liste) ->
- {Heap, N} = createHeap(Liste),
- createList(Heap, N+1).
- createList({}, _N)
- ->[];
- createList(Heap={Z, _L, _R}, N)
- -> HeapNeu = removeMin(Heap, calcPath(N-1)), createList(HeapNeu, N-1)++[Z].
- createHeap(Liste=[H|T]) ->
- Heap = {H, {}, {}},
- createHeap(Heap, T, 1).
- createHeap(Heap, [], N) -> {Heap, N};
- createHeap(Heap, Liste=[H|T], N) ->
- NewHeap = insertHeap(Heap, H,calcPath(N+1)),
- createHeap(NewHeap, T, N+1).
- % 4 8 3 9 6
- %insertHeap({}, E,[]) -> {E,{}, {}};
- insertHeap(Heap={Zh, L, R}, E, Steps = [l|[]]) when E > Zh ->
- {E, Lneu={Zh, {},{} }, {}};
- insertHeap(Heap={Zh, L, R}, E, Steps = [r|[]]) when E > Zh ->
- {E, L, {Rneu=Zh,{},{}}};
- insertHeap(Heap={Zh, L, R}, E, Steps = [l|[]]) when E =< Zh ->
- {Zh, Lneu={E, {},{} }, {}};
- insertHeap(Heap={Zh, L, R}, E, Steps = [r|[]]) when E =< Zh ->
- {Zh, L, {Rneu=E,{},{}}};
- insertHeap(Heap={Zh, L, R}, E, Steps = [l|T]) when E > Zh ->
- {E, insertHeap(L,Zh, T), R};
- insertHeap(Heap={Zh, L, R}, E, Steps = [r|T]) when E > Zh ->
- {E, L, insertHeap(R,Zh, T)};
- insertHeap(Heap={Zh, L, R}, E, Steps = [l|T]) when E =< Zh ->
- {Zh, insertHeap(L,E, T), R};
- insertHeap(Heap={Zh, L, R}, E, Steps = [r|T]) when E =< Zh ->
- {Zh, L, insertHeap(R,E, T)}.
- peekLast(_Heap={Z, L, R}, [r | []])
- -> {E, _, _ } = R,
- {{Z, L, {}}, E};
- peekLast(_Heap={Z, L, _R}, [l | []])
- -> {E, _, _ } = L,
- {{Z, {}, {}}, E};
- peekLast(_Heap={Z, L, R}, [l | Schritte])
- -> {Lneu, E} = peekLast(L, Schritte),
- {{Z, Lneu, R}, E};
- peekLast(_Heap={Z, L, R}, [r | Schritte])
- -> {Rneu, E} = peekLast(R, Schritte),
- {{Z, L, Rneu}, E}.
- removeMin(_Heap={_Z, {}, {}}, [])
- -> {};
- removeMin(Heap={_Z, _L ,_R}, Schritte)
- -> {{_Zneu, Lneu, Rneu}, E} = peekLast(Heap, Schritte),
- toHeap ({E, Lneu, Rneu}).
- toHeap(_Heap={Z, _L={LZ, _, _}, {} }) when LZ>Z
- -> {LZ, {Z, {}, {}}, {}};
- toHeap(_Heap={Z, L={LZ, _LL, _LR}, _R={RZ, RL, RR}}) when RZ>LZ, RZ>Z
- -> {RZ, L, toHeap({Z, RL, RR})};
- toHeap(_Heap={Z, _L={LZ, LL, LR}, R={RZ, _RL, _RR}}) when LZ>RZ, LZ>Z %links ist am grossten
- -> {LZ, toHeap({Z, LL, LR}), R};
- toHeap(Heap) %%ende, Z ist am grossten
- -> Heap.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement