#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2012
    Posts
    13
    Rep Power
    0

    Linked list sorting


    Code:
    Gll * fun_s(Gll* node,comp_fun comp )
    {
        if(!node || !(node -> next) ){
            printf("less than two node in the list\n");
            return node;
        }
        //int ints[] = {12,2,3,4,5,6,1,8,9,10,11,7};
        //int ints[] = {1,12,2,3,5,8,4,9,6,10,11,7};
        while ( 1 ){
    
            Gll *prev,*curr,*nxt ;
            int swap = 0;
            prev = curr = node ;
            nxt = curr->next;
            while( nxt ) {
                if ( (*comp)(curr->data ,nxt->data) > 0) {
                    curr -> next = nxt -> next;
                    nxt -> next = curr;
                    if(curr == node){
                        prev = node = nxt;
                    }else{
                        prev -> next = nxt;
                        prev = nxt ;
                    }
                    swap = 1;
                }else {
                    prev = curr;
                }
                curr = prev -> next ;
                nxt = curr -> next;
    
            }
            if(!swap)
                break;
        }
            return node;
    }
    This is program which sorts a linked lists if its unsorted and retains
    the same if its sorted.

    But the program is not so efficient in the sense that its kind of bubble
    sort.In every iteration the next highest element will get sorted out.
    But i am not able have a mechanism which can reduce the no of iterations.
    That means there is no need to check for already sorted elements.

    Please suggest if any other best or optimised mechanism is available.

    Also please let me know if you find any problem( does not work for any combination of input)
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    Bubblesort is one of the worst sorting algorithms, either for arrays or for linked lists. Mergesort, on the other hand, is a pretty good option for sorting a linked list:

    - doesn't require random access
    - O(n*log(n)) worst case
    - doesn't require allocating extra memory

    The algorithm:

    1. Divide the list in the middle into two lists of close-to-equal size.
    2. Recursively sort the two lists.
    3. Merge the sorted lists into a single sorted list.
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2012
    Posts
    156
    Rep Power
    34
    One option is to copy the list to an array, sort the array (using qsort), and copy back to the list.
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2012
    Posts
    13
    Rep Power
    0
    Thanks for the replies.
    Yeah, i understand.
    Before asking here i just googled, many people suggested only these two methods.

    I am going to try for any one of these methods.

IMN logo majestic logo threadwatch logo seochat tools logo