Linked list insertion sort

Question

I'm not very advanced in the sorting part of programming yet, so I was looking for some help with my algorithm.

void sortList()
{
    Item_PTR tmpNxt = current->nextItem;
    Item_PTR tmpPTR = current;
    int a, tmp;

    while(tmpNxt != NULL)
    {   
        a = tmpPTR->value;
        while(tmpNxt != tmpPTR && tmpNxt->value < a)
        {
            tmp = a;
            tmpPTR->value = tmpNxt->value;
            tmpNxt->value = tmp;
            tmpPTR = tmpPTR->nextItem;
        }
        tmpPTR = current;   
        tmpNxt = tmpNxt->nextItem;
    }

}

The list state before sorting: 9 8 7 6 5 4 3 2 1 after sorting: 1 9 8 7 6 5 4 3 2

I'm not sure why...I've played computer a lot on paper and I feel like it should work...but maybe other eyes will spot the problem.

Current is a global pointer that will always have the location of the first/ top element in the list.

Answer 1

This is because the function sortList() is not changing current, the "global" variable denoting the list head.

Please don't use a global variable, and certainly not for a linked list head. (What will you do when you need two lists?)

I would redesign the sortList() function to either one of the following:

/* sort the list pointed to by phead and return the new head after sorting */
Item_PTR sortList( Item_PTR phead );

/* sort the list pointed to by *pphead */
void sortList( Item_PTR * pphead );

Also, make yourself familiar (even if you can't use them in the immediate project) to the interface of C++ Standard Library for lists, std::list link

Answer 2

Not an answer to your question, but too long for a comment:

When sorting linked lists, you often don't want to swap node values, but re-link the list instead. For example, if you create an ad-hoc list by adding a next member to an existing structure, you most likely don't want the structure's address to change.

Because linked lists don't allow efficient random access, you're restricted to online algorithms, specifically insertion sort and mergesort. Your choice of insertion sort is the correct one for a beginner, as it's easier to implement (but slower).

If you want to switch to a re-linking version, it might be a good idea to split your algorithm in two parts: an insert() function which inserts a node into the list in order, and a sort() function, which re-builds an unordered list.

My implementation of insertion sort and mergesort for generic lists can be found at here, but becaue of its generality, the code is somewhat harder to read.