Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package ads1ss11.pa1;
- /**
- * Sorter Klasse in der die Methode {@link #mergesort(DoublyLinkedList, int)}
- * implementiert werden soll.
- *
- * <p>
- * In dieser Klasse müssen Sie Ihren Code einfügen und die Method
- * {@link #mergesort(DoublyLinkedList, int)} implementieren.
- * </p>
- *
- * <p>
- * Sie können beliebige neue Variablen und Methoden in dieser Klasse
- * hinzufügen.
- * </p>
- */
- public class Sorter {
- /**
- * MergeSort Implementierung
- *
- * @param in Unsortierte Eingabefolge
- * @param numOfElements Größe der Eingabefolge
- * @return Sortiterte Eingabefolge
- */
- public DoublyLinkedList mergesort
- (DoublyLinkedList in, int numOfElements)
- {
- ListElement start = in.first;
- ListElement end = sort(start, numOfElements);
- in.first = end.next;
- return in;
- }
- /*
- * merge die beiden listen die mid bzw end als letztes element haben
- * m = laenge der ersten liste (vordere)
- * len = laenge der beiden liste zusammen
- * returned letztes element der gemergeden liste
- *
- * merge wird vom rechts nach links in der liste durchgefuehrt
- */
- private ListElement merge
- (ListElement mid, ListElement end, int m, int len)
- {
- ListElement lit = mid, rit = end;
- int l = m, r = len;
- while( l > 0 && r > m ){
- if( lit.getKey() <= rit.getKey() ){
- rit = rit.prev;
- r -= 1;
- }
- else{
- ListElement ritnext = rit.next;
- ListElement litprev = lit.prev;
- litprev.next = lit.next; lit.next.prev = litprev;
- rit.next = lit; lit.prev = rit;
- ritnext.prev = lit; lit.next = ritnext;
- if( rit == end )
- end = lit;
- l -= 1;
- lit = litprev;
- }
- }
- return end;
- }
- private ListElement sort(ListElement start, int len)
- {
- if( len == 1 )
- return start;
- int m = len/2;
- ListElement mid = sort(start, m);
- ListElement end = sort(mid.next, len-m);
- return merge(mid, end, m, len);
- }
- }
Add Comment
Please, Sign In to add comment