basic insertion sort in linked list with logic problem (maybe it is because pointer)

One of the most important difference between a linked list and an array is that it is sometimes required to handle the first element as a special case.

Here is a fixed version of your sorting method :

void insertionSort()
{
    bool breakByCompare;
    Node* keyptr;
    Node* judgeptr;
    int key;
    for(keyptr = list->getNext(); keyptr != NULL;  keyptr = keyptr->getNext()){
        
        key = keyptr->getData();
        breakByCompare = 0;
        
        // I replaced judgeptr->getPre() by judgeptr in the condition
        // to allow the backward loop to go until the root
        for(judgeptr = keyptr->getPre() ; judgeptr != NULL;  judgeptr= judgeptr->getPre()){
            
            if(judgeptr->getData() > key){
                judgeptr->getNext()->setData(judgeptr->getData());
                cout << judgeptr->getData() << " , " << key << endl;
            }
            else break;
        }
        // Here is the special case : we must support a null judgeptr 
        // and replace its next element by the list
        if (judgeptr) judgeptr->getNext()->setData(key);
        else list->setData(key);
    }
}

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top