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;
}

I think it would be a lot easier to move the node's data around instead of trying to move the nodes themselves. Moving the nodes means you have to correct all the links. You don't have to do that if you just move the data.

This article has been dead for over six months. Start a new discussion instead.