Guest User

Untitled

a guest
Dec 11th, 2017
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.99 KB | None | 0 0
  1. package ads1ss11.pa1;
  2.  
  3. /**
  4. * Sorter Klasse in der die Methode {@link #mergesort(DoublyLinkedList, int)}
  5. * implementiert werden soll.
  6. *
  7. * <p>
  8. * In dieser Klasse m&uuml;ssen Sie Ihren Code einf&uuml;gen und die Method
  9. * {@link #mergesort(DoublyLinkedList, int)} implementieren.
  10. * </p>
  11. *
  12. * <p>
  13. * Sie k&ouml;nnen beliebige neue Variablen und Methoden in dieser Klasse
  14. * hinzuf&uuml;gen.
  15. * </p>
  16. */
  17.  
  18. public class Sorter {
  19.  
  20. /**
  21. * MergeSort Implementierung
  22. *
  23. * @param in Unsortierte Eingabefolge
  24. * @param numOfElements Gr&ouml;&szlig;e der Eingabefolge
  25. * @return Sortiterte Eingabefolge
  26. */
  27. public DoublyLinkedList mergesort
  28. (DoublyLinkedList in, int numOfElements)
  29. {
  30. ListElement start = in.first;
  31. ListElement end = sort(start, numOfElements);
  32. in.first = end.next;
  33. return in;
  34. }
  35.  
  36.  
  37. /*
  38. * merge die beiden listen die mid bzw end als letztes element haben
  39. * m = laenge der ersten liste (vordere)
  40. * len = laenge der beiden liste zusammen
  41. * returned letztes element der gemergeden liste
  42. *
  43. * merge wird vom rechts nach links in der liste durchgefuehrt
  44. */
  45. private ListElement merge
  46. (ListElement mid, ListElement end, int m, int len)
  47. {
  48. ListElement lit = mid, rit = end;
  49. int l = m, r = len;
  50.  
  51. while( l > 0 && r > m ){
  52. if( lit.getKey() <= rit.getKey() ){
  53. rit = rit.prev;
  54. r -= 1;
  55. }
  56. else{
  57. ListElement ritnext = rit.next;
  58. ListElement litprev = lit.prev;
  59.  
  60. litprev.next = lit.next; lit.next.prev = litprev;
  61. rit.next = lit; lit.prev = rit;
  62. ritnext.prev = lit; lit.next = ritnext;
  63.  
  64. if( rit == end )
  65. end = lit;
  66.  
  67. l -= 1;
  68. lit = litprev;
  69. }
  70. }
  71.  
  72. return end;
  73. }
  74.  
  75.  
  76. private ListElement sort(ListElement start, int len)
  77. {
  78. if( len == 1 )
  79. return start;
  80.  
  81. int m = len/2;
  82. ListElement mid = sort(start, m);
  83. ListElement end = sort(mid.next, len-m);
  84.  
  85. return merge(mid, end, m, len);
  86. }
  87. }
Add Comment
Please, Sign In to add comment