Selection Sort Link List

**Chanakya** · 02-08-2013

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

**iMalc** · 02-08-2013

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.

**Chanakya** · 02-09-2013

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.

**Salem** · 02-09-2013

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.

**iMalc** · 02-09-2013

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.

**MacNilly** · 02-11-2013

To make this code more efficient:

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

Thread: Selection Sort Link List

Thread Tools

Search Thread

Display

Selection Sort Link List

Similar Threads

cannot figure out problem: selection sort in linked list

How to sort a link list alphabetically? ( C Programming thru Linux gcc)

linked list sort with variable struct selection field

Link list sort no work.

merge sort and selection sort and time spent on both

Tags for this Thread