Selection Sort Link List

This is a discussion on Selection Sort Link List within the C++ Programming forums, part of the General Programming Boards category; Help me make this code more efficient. Code: void llist::sort() { int val,val1; for(node *p = first, *p1, *pos; p->next ...

  1. #1
    Registered User
    Join Date
    Jun 2012
    Location
    New Delhi, India, India
    Posts
    6

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

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Jun 2012
    Location
    New Delhi, India, India
    Posts
    6
    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.
    Last edited by Chanakya; 02-09-2013 at 04:12 AM.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,452
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    311
    To make this code more efficient:

    1) Use an array instead of a linked list,
    2) Then use merge sort instead of selection sort
    GCC on Fedora Core 10

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 05-29-2011, 01:23 PM
  2. Replies: 2
    Last Post: 07-20-2010, 08:09 PM
  3. Replies: 2
    Last Post: 01-17-2009, 09:48 PM
  4. Link list sort no work.
    By xddxogm3 in forum C++ Programming
    Replies: 8
    Last Post: 10-15-2003, 11:42 PM
  5. merge sort and selection sort and time spent on both
    By misswaleleia in forum C Programming
    Replies: 3
    Last Post: 06-04-2003, 02:24 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21