Selection Sort Link List

Help me make this code more efficient.

Code:

---

void llist::sort()
{
    int val,val1;
    for(node *p = first, *p1, *pos; p->next != NULL; p = p->next)
    {
        val = p->info;
        pos = p;
        for(node *q = p; q->next != NULL; q = q->next)
        {
            val1 = (*(q->next)).info;
            if(val1 < val)
            {
                val = val1;
                pos = q;
            }
        }
        if(val != p->info)
        {
            node *temp = pos->next;
            if( temp!= NULL)
                pos->next = temp->next;
            else
                pos->next = NULL;
            if(pos != p)
            {
                temp->next = p->next;
                p->next = pos->next;
                pos->next = p;
            }
            else
                temp->next = p;

            if(p == first)
                first = temp;
            else
                p1->next = temp;
            p = temp;
        }
        p1 = p;
    }
}

---

That looks like an average implementation of selection sort for a linked list. There are probably only minor efficiency improvements possible. As long as its working correctly, its probably good enough as-is.

However, Selection Sort is only somewhat efficient when used to sort short lists. When sorting anything of substantial length (e.g. greater than 20 items), then a better algorithm is required. I recommend Merge Sort, or if you have a really really large number of items, then Bucket Sort. Those can offer performance hundreds or thousands of times faster, depending on the size of your list.

It is working fine.
I was required to use selection sort. However I was wondering if the number of loop executions, the number of if statements or the number of pointers used could be reduced.

Save the optimisations for the compiler.

You might (after several days) manage to squeeze out some variable or statement, but what would be the point of that?

- The code becomes much harder to read, to test, to fix
- Your boss/tutor is angry because you wasted time doing this, rather than getting on with some other work which needed doing.

If it's easy to read, and it works - then that's good enough for most people.

If (and I do mean IF), this seems to be a performance bottleneck when you profile the code, only then do you set about trying to improve it.

Well I do have code that does Selection Sort on a linked list which uses only 1 while, 1 do..while, 2 ifs, and 1 else. Without a certain hack/trick it would take one more if + else.
So yes it can be reduced a bit. But showing how would take all the fun out of it.

To make this code more efficient:

1) Use an array instead of a linked list,
2) Then use merge sort instead of selection sort