• 02-08-2013
Chanakya
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;     } }```
• 02-08-2013
iMalc
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.
• 02-09-2013
Chanakya
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.
• 02-09-2013
Salem
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.
• 02-09-2013
iMalc
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.
• 02-11-2013
MacNilly
To make this code more efficient: