I am having trouble implementing a sort function for this link list.
This list works just fine. I just want to be able to sort by name.
When I run the sort function I get back this;
-------IN-------
bb
aaa
aaaa
aaaaa
aa
bbb
b
-------OUT-------
bb
bbb
--------------
I have included what I have been using to do the sorting but can not locate the error. If anyone could help I would be very appreciative.
template<class Type>
void slinkedListType<Type>::M_Sort(nodeType<Type> **head) {
nodeType<Type> *leftHead = NULL;
nodeType<Type> *rightHead = NULL;
if(!head) {
// printf("NULL HEAD\n");
return;
}
if(!*head) {
// printf("NULL HEAD ptr\n");
return;
}
if(!(*head)->link) {
// printf("NULL HEAD ptr link\n");
return;
}
// printf("-------------------===============\n");
// print();
leftHead = *head;
rightHead = *head;
//Keep splitting the list in the middle
SplitLinkedList(*head,&leftHead,&rightHead);
M_Sort(&leftHead);
M_Sort(&rightHead);
//head now points to the merged list
*head = Merge(&leftHead,&rightHead);
}
template<class Type>
nodeType<Type>* slinkedListType<Type>::Merge(nodeType<Type> **leftHead, nodeType<Type> **rightHead) {
//We need 2 pointers in both the lists to merge the nodes
nodeType<Type> *leftFront = NULL;
nodeType<Type> *leftRear = NULL;
nodeType<Type> *rightFront = NULL;
nodeType<Type> *rightRear = NULL;
//Do the Null Pointer Checks
if(!leftHead) {
return NULL;
}
if(!*leftHead) {
return NULL;
}
if(!rightHead) {
return *leftHead;
}
if(!*rightHead) {
return *leftHead;
}
//Initialize the pointers in left, right Lists
leftFront = *leftHead;
leftRear = NULL;
rightFront = *rightHead;
rightRear = NULL;
// If there is only one node in both the lists
// then simply do a check and merge the nodes
if(leftFront->link == NULL && rightFront->link == NULL) {
if(strcmp(leftFront->info.getName(), rightFront->info.getName()) < 0) {
leftFront->link = rightFront;
} else {
rightFront->link = leftFront;
*leftHead = rightFront;
}
return *leftHead;
}
//If either of the list has more than 1 node
/*The idea here is to have a rightFront pointer as a checkpoint
and keep moving the leftFront pointer until you reach a node
on the right list whose value is > leftFront->info.getName(), then merge at that node using
the rear pointers */
while(leftFront != NULL && rightFront != NULL) {
//keep traversing until you hit a node on the left list
//such that its value is > the value on right list
while(leftFront != NULL && strcmp(leftFront->info.getName(),rightFront->info.getName()) < 0) {
leftRear = leftFront;
leftFront = leftFront->link;
}
// check for NULL pointers
if(leftFront != NULL && rightFront != NULL) {
/*If the rear pointer is pointing to NULL it indicates
the data on the rightlist to merge is supposed to get
to the beginning of the merged list */
if(leftRear == NULL) {
rightRear = rightFront;
rightFront = rightFront->link;
leftRear = rightRear;
leftRear->link = leftFront;
*leftHead = rightRear;
if(!rightFront) {
break;
}
} else {
//Else the node is supposed to merged in between / end of the merged list
rightRear = rightFront;
rightFront = rightFront->link;
leftRear->link = rightRear;
leftRear = leftRear->link;
leftRear->link = leftFront;
if(!rightFront) {
break;
}
}
if(strcmp(leftFront->info.getName(), rightFront->info.getName()) < 0) {
leftRear = leftFront;
leftFront = leftFront->link;
} else {
continue;
}
}
}// end of while
if(leftFront == NULL && rightFront != NULL) {
leftRear->link = rightFront;
}
return *leftHead;
}
void slinkedListType<Type>::SplitLinkedList(nodeType<Type> *head,nodeType<Type> **leftHead,nodeType<Type> **righ
tHead) {
nodeType<Type> *leftTemp = NULL;
nodeType<Type> *rightTemp = NULL;
if(!head) {
return;
}
if(!leftHead || !rightHead) {
return;
}
if(!*leftHead || !*rightHead) {
return;
}
leftTemp = head;
rightTemp = head;
if(!(rightTemp->link)) {
*rightHead = NULL;
return;
}
while(rightTemp->link != NULL) {
rightTemp = rightTemp->link;
if(rightTemp->link != NULL) {
leftTemp = leftTemp->link;
rightTemp = rightTemp->link;
} else {
*rightHead = leftTemp->link;
leftTemp->link = NULL;
}
}
if(*rightHead == head) {
*rightHead = leftTemp->link;
leftTemp->link = NULL;
}
leftTemp = *leftHead;
rightTemp = *rightHead;
}