c++ - Merge sort does not split the right side of the list -
like title states, merge sort splits left side. else works fine, including merge function. can't figure out why. appreciate help. in list includes: 7, 4, 10, 2, 6, 1, 3, 7, 11, 5 outputs 1, 2, 3, 4, 6, 7, 7, 10, 11, 5
edit: added rest of class.
#include <iostream> #include <string> using namespace std; class linkedlist { private: class node { public: int data; node * next; node * prev; node(int x) { data = x; next = null; prev = null; } }; node * head; node * tail; node * split() { node * finger = head; node * fast = head->next; while (fast != null) { fast = fast->next; if (fast != null) { fast = fast->next; finger = finger->next; } } tail = finger->next; node * splitb = tail; splitb->prev = null; finger->next = null; return splitb; } node * merge(node * a, node * b) { linkedlist m; while(a != null || b != null) { if(b == null) { if(m.head != null) { a->prev = m.tail; m.tail->next = a; m.tail = a; } else { m.head = a; m.tail = m.head; } = a->next; } else if(a == null) { if(m.head != null) { b->prev = m.tail; m.tail->next = b; m.tail = b; } else { m.head = b; m.tail = m.head; } b = b->next; } else if (a->data < b->data) { if(m.head == null) { m.head = a; m.tail = m.head; } else { a->prev = m.tail; m.tail->next = a; m.tail = a; } = a->next; } else { if(m.head == null) { m.head = b; m.tail = m.head; } else { b->prev = m.tail; m.tail->next = b; m.tail = b; } b = b->next; } } return m.head; } node* mergesort(node * a) { if (head == null || head->next == null) { return a; } else { node * b = split(); node* right = mergesort(a); node* left = mergesort(b); return merge(right, left); } } public: linkedlist() { head = null; tail = null; } void push_back(int x) { node * baby = new node(x); if( head == null ) { head=baby; tail=baby; } else { baby->prev = tail; tail->next = baby; tail = baby; } } void mergesort() { head = mergesort(head); } bool empty() { if (head == null) return true; else return false; } int pop() { int popme = head->data; node * deleteme = head; if (head->next == null) { head = null; tail = null; delete deleteme; return popme; } else { head = head->next; head->prev = null; delete deleteme; return popme; } } //test void display() { node * finger = head; while(finger!=null) { cout << finger->data << endl; finger = finger->next; } } };
to merge sort going have break list. example splitting on head , tail pointless. splitting on whole list, not increasingly smaller portions of list. split have this:
void split(node *& a, node *& b) { node * finger = a; node * fast = a->next; while (fast != null) { fast = fast->next; if (fast != null) { fast = fast->next; finger = finger->next; } } b = finger->next; b->prev->next = null; b->prev = null; } i recommend changing variable names fast , finger more descriptive.
merge , mergesort require similar modification.
edited post things c++ way. sorry that.
Comments
Post a Comment