Advertisement
exnon

heapsort

Dec 9th, 2020
3,591
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Erlang 1.86 KB | None | 0 0
  1. -module(heapsort).
  2. -export([hsort/1]).
  3. % Kodierung des Feldes: Nachfolger von Position i ist 2*i links und 2*i+1 rechts
  4. % berechnet den Pfad zur ersten leeren Position
  5. % l steht fuer links, r fuer rechts
  6. % Beispiel: sort:calcPath(1). --> []
  7. %       sort:calcPath(2). --> [l]
  8. %       sort:calcPath(3). --> [r]
  9. %       sort:calcPath(4). --> [l,l]
  10. %       sort:calcPath(5). --> [l,r]
  11. %       sort:calcPath(6). --> [r,l]
  12. %       sort:calcPath(7). --> [r,r]
  13. calcPath(Number) -> calcPath(Number,[]).
  14. % aktuelle Position ist Wurzel
  15. calcPath(1,Accu) -> Accu;
  16. % aktuelle Position ist gerade
  17. calcPath(Number,Accu) when Number rem 2 =:= 0 -> calcPath(Number div 2,[l|Accu]);
  18. % aktuelle Position ist ungerade
  19. calcPath(Number,Accu) when Number rem 2 =/= 0 -> calcPath((Number-1) div 2,[r|Accu]).  
  20.  
  21. hsort(Liste) ->
  22.     {Heap, N} = createHeap(Liste).
  23. %   createList(Heap, N+1).
  24.    
  25. createHeap(Liste=[H|T]) ->
  26.     Heap = {H, {}, {}},
  27.     createHeap(Heap, T, 1).
  28. createHeap(Heap, [], N) -> {Heap, N};
  29. createHeap(Heap, Liste=[H|T], N) ->
  30.     NewHeap = insertHeap(Heap, H,calcPath(N+1)),
  31.     createHeap(NewHeap, T, N+1).
  32. % 4 8 3 9 6
  33. %insertHeap({}, E,[]) -> {E,{}, {}};
  34. insertHeap(Heap={Zh, L, R}, E, Steps = [l|_]) when E > Zh ->
  35.     {E, Lneu={Zh, {},{} }, {}};
  36. insertHeap(Heap={Zh, L, R}, E, Steps = [r|_]) when E > Zh ->
  37.     {E, L, {Rneu=Zh,{},{}}};
  38.    
  39. insertHeap(Heap={Zh, L, R}, E, Steps = [l|_]) when E =< Zh ->
  40.     {Zh, Lneu={E, {},{} }, {}};
  41. insertHeap(Heap={Zh, L, R}, E, Steps = [r|_]) when E =< Zh ->
  42.     {Zh, L, {Rneu=E,{},{}}};
  43.    
  44. insertHeap(Heap={Zh, L, R}, E, Steps = [l|T]) when E > Zh ->
  45.     {E, insertHeap(L,Zh, T), R};
  46. insertHeap(Heap={Zh, L, R}, E, Steps = [r|T]) when E > Zh ->
  47.     {E, L, insertHeap(R,Zh, T)};   
  48.  
  49. insertHeap(Heap={Zh, L, R}, E, Steps = [l|T]) when E =< Zh ->
  50.     {Zh, insertHeap(L,E, T), R};
  51. insertHeap(Heap={Zh, L, R}, E, Steps = [r|T]) when E =< Zh ->
  52.     {Zh, L, insertHeap(R,E, T)}.
  53.  
  54.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement