Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- -module(heapsort).
- -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).
- 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)}.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement