Like Tree2Likes
  • 1 Post By stahta01
  • 1 Post By iMalc

how to sort datas in linked list and arrange them highest to lowest. [LONG CODE]

This is a discussion on how to sort datas in linked list and arrange them highest to lowest. [LONG CODE] within the C Programming forums, part of the General Programming Boards category; Hi, i am making a program that reads a file from .txt and print them out using linked list. However, ...

  1. #1
    Registered User
    Join Date
    May 2013
    Posts
    59

    how to sort datas in linked list and arrange them highest to lowest. [LONG CODE]

    Hi, i am making a program that reads a file from .txt and print them out using linked list. However, i need to sort them from the highest price to lowest price. I have an example here but i dont really understand, it there anyway to make it simpler?

    you might want to skip straight to the bottom part of the code 1st. the top parts are just the functions that the example given used and some of my functions which im required to use.

    Code:
    /* my structs */
    
    typedef struct{
        Node *head;
        Node *tail;
        Node *iterator;
        int size;
    } List;
    
    typedef struct {
        char *id;
        double weight;
        double shippingPrice;
    }Container;
    
    typedef struct Node {
        void *data;
        struct Node *next;
    } Node;
    
    
    /* my functions */
    
    void nd_setNext( Node *node, Node *next)
    {
        node->next = next;
    }
    
    Node *nd_getNext( Node *node)
    {
        return node->next;
    }
    
    void *nd_getData( Node *node )
    {
        return node->data;
    }
    
    void *lst_next(List *lst)
    {
        if(lst->iterator != NULL)
        {
            lst->iterator = node_getNext(lst->iterator);
            
            if(lst->iterator != NULL)
                return node_getData(lst->iterator);
                
        }
        return NULL;
    }       
        
    void *lst_first(List *lst)
    {
        lst->iterator = lst->head;
        
        if(lst->iterator != NULL)
            return node_getData(lst->iterator);
            
        else
            return NULL;
    }       
    
    void lst_add( List *lst, void *data)
    {
        lst_append(lst, data);
    }
    
    void lst_append( List *lst, void *data)
    {
        Node *newCnrNode = node_new(data, NULL);
        
        if (lst->size == 0)
            lst->head = newCnrNode;
            
        else                    
            lst->tail->next = newCnrNode;
            
       
        lst->tail = newCnrNode;
        
        lst->size++;
    }
    
    List *lst_new(void)
    {
        List *list = (List *)malloc(sizeof(List));
        list->head = NULL;
        list->tail = NULL;
        list->iterator = NULL;
        list->size = 0;
        
        return list;
    }
    
    
    /* functions that i have to use in the sort(high to low) function */
    
    double cnr_getShippingPrice(Container * contain)
    {
        return contain->shippingPrice;
    }
    
    /* functions used by the example given */
    
    int compareOrbits(const void *plnt1, const void *plnt2)
    {    
        int b1 = plnt_getOrbit((const Planet *)plnt1);
        int b2 = plnt_getOrbit((const Planet *)plnt2);
        return b1 - b2;
    }
    
    void orderPlanets(List **list)
    {
        Planet * tempPlanet;
        
         List *sorted = lst_new();
        
       for (tempPlanet = lst_first(*list); 
                            tempPlanet != NULL; 
                                        tempPlanet = lst_next(*list))
        {
            lst_insertInOrder(sorted, tempPlanet, compareOrbits); /*this function that i dont understand */
        }  
        
        lst_delete(*list);
        
        *list = sorted;
    }
    
    /* part which i dont understand */
    void lst_insertInOrder(List *lst, void *data,
                           int(*compare)(const void *data1, const void *data2))
    {
        Node *current = lst->head, *previous = NULL;
        int smaller;
        
       
        if(lst_isEmpty(lst))
            lst_add(lst, data);
        else
        {
           Node * newNode = nd_new(data, NULL);
              
            current = lst->head;
            smaller = compare(data, nd_getData(current)) < 0;
            while(nd_getNext(current) != NULL && !smaller)       /* nd_getNext is actually the node_getNext shown above */
            {
                previous = current;
                current = nd_getNext(current);
                smaller = compare(data, nd_getData(current)) < 0; /* ???? */
            }
            
          if(previous == NULL && smaller) 
             {
                /* Then new node is head */
                nd_setNext(newNode, lst->head);
                lst->head = newNode;
             }
             else if( smaller)
             {
                nd_setNext(newNode, nd_getNext(previous));
                nd_setNext(previous, newNode);
             }
             else 
             {
                lst->tail->next = newNode;        
                
                lst->tail = newNode;
             }
             
             lst->size++;          
        }
    }
    i know its long but im afraid that i might miss out some things.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,333
    I'm just trying to imagine a program where "Shipping containers" and "planets" can co-exist.

    It looks like a rag-bag of code copy/pasted from all over the place.

    > smaller = compare(data, nd_getData(current)) < 0; /* ???? */
    What about it?
    - the fact that compare is a function pointer?
    - the use of a relop in an assignment?

    Would this make it any clearer?
    Code:
    if ( compare(data, nd_getData(current)) < 0 ) {
      smaller = 1;
    } else {
      smaller = 0;
    }
    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.

  3. #3
    Registered User
    Join Date
    Apr 2013
    Posts
    1,160
    Code:
            while(nd_getNext(current) != NULL && !smaller)       /* nd_getNext ... */
            {
                previous = current;
                current = nd_getNext(current);
                smaller = compare(data, nd_getData(current)) < 0; /* ???? */
            }
    Note that the while loop conditional expression ends with "... && !smaller", and the last statement "smaller = compare(...)" sets smaller if (data - current->data) < 0, which means data is less than current->data, so the while loop runs as long as current != NULL and data is greater than or equal to current->data.

    - - - comments - - -

    Currently the code only inserts nodes into a sorted list, to create a sorted list. There is no function to sort an unsorted list.

    Iterator is not normally part of a List structure and is usually a separate variable, that would be passed to and/or returned from the lst_...() functions.

    If the next pointer is the first member of a node structure, then common code (with casting of node pointers) can be used to operate on lists of various types of nodes.
    Last edited by rcgldr; 08-12-2013 at 11:25 AM.

  4. #4
    Registered User
    Join Date
    May 2013
    Posts
    59
    Quote Originally Posted by Salem View Post
    I'm just trying to imagine a program where "Shipping containers" and "planets" can co-exist.

    It looks like a rag-bag of code copy/pasted from all over the place.

    [/code]
    planet is the example i've taken. Container is what i am doing now.

  5. #5
    Registered User
    Join Date
    May 2013
    Posts
    59
    and is there any other way to sort my list according to the shipping price or at least make the code shown simpler?

  6. #6
    Registered User
    Join Date
    May 2009
    Posts
    2,371
    Quote Originally Posted by Salem View Post
    I'm just trying to imagine a program where "Shipping containers" and "planets" can co-exist.
    It is clearly an Interplanetary Shipping Company.

    Tim S.
    iMalc likes this.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    1,160
    Quote Originally Posted by Alexius Lim View Post
    and is there any other way to sort my list according to the shipping price or at least make the code shown simpler?
    The code is not sorting a list, it's creating a list in sorted order by inserting a node into the list one at a time. It's not the fastest method since on average it traverses through 1/2 of the list for each insertion, but it is simple enough.

    There is a faster method for doing this, but it takes a bit more memory. You'll need an array of list structures where each list contains 2^n nodes, plus one temp list. Instead of inserting into a single list, the nodes are stored into a single node list, then any existing lists are merged into ever larger lists until an empty list or the last list is found in the array, where the merged list is stored. This is how the standard template library in C++ implements a list sort in the case of Visual Studio.

    Another alternative, is to just append to a list, resulting in an unsorted list, then generate an array of pointers to all the nodes, then sort the list using the pointers using whatever sort algorithm you like. It's a bit of a cheat though and again takes more memory (one pointer per node).

  8. #8
    Registered User
    Join Date
    Apr 2013
    Posts
    1,160
    Quote Originally Posted by rcgldr View Post
    an array of list structures where each list contains 2^n nodes ...
    To clarify this, each array list member contains 2^i nodes, where i is the index into the array, so that array[0] list size is 1 node, array[1] list size is 2 nodes, array[2] list size is 4 nodes, array[3] list size is 8 nodes, array[4] list size is 16 nodes, ..., array[31] list size is 2,147,483,648 nodes, ... . So an array size of 32 should be enough. I've done this using a list structure that only contains a single pointer to the first node of a single linked list (no tail pointer is needed in this case).

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Or you just write a simple top-down recursive merge sort.

    But really, unless this assignment has a requirement for handling over 100 or so items, a basic insertion scheme should be good enough.

    I agree with Salem that this would appear to be franken-code, parts of which are written by someone who understands function pointers well enough, but the OP has not realised that he just needs to pass in an appropriate comparison function. But really we're told this anyway, as nobody would say that they don't understand that they themselves wrote.
    Or at least not so soon after writing it.

    So um dude, look into compareOrbits, which you might want to rename by the way. It tells the other bit of code how you want to order the items.
    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"

  10. #10
    Registered User
    Join Date
    Apr 2013
    Posts
    1,160
    Quote Originally Posted by rcgldr View Post
    each array list member contains 2^i nodes, where i is the index into the array
    Quote Originally Posted by iMalc View Post
    Or you just write a simple top-down recursive merge sort.
    I'm not aware of an efficient method to split a linked list into two equal sub-lists, and to do this repeatedly. Assuming the count of nodes is known, you'd have to iterate through a list (count/2) times to find the mid point and do this recursively until list size became 1 before merging begins.

    Even for arrays, recursive merge sort "wastes" time by recursively splitting arrays into sub-arrays until an array size of 1 is achieved before any merging occurs. A bottom up merge skips this step by just considering an array of size n to be n arrays of size 1 (or n/m arrays of size m).
    Last edited by rcgldr; 08-13-2013 at 04:28 AM.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Quote Originally Posted by rcgldr View Post
    I'm not aware of an efficient method to split a linked list into two equal sub-lists, and to do this repeatedly. Assuming the count of nodes is known, you'd have to iterate through a list (count/2) times to find the mid point and do this recursively until list size became 1 before merging begins.
    That is largely correct. You can do one pass up front to count the number of items in the list and halve the remaining work of each split thereafter, though I have not bothered with this.

    Even for arrays, recursive merge sort "wastes" time by recursively splitting arrays into sub-arrays until an array size of 1 is achieved before any merging occurs. A bottom up merge skips this step by just considering an array of size n to be n arrays of size 1 (or n/m arrays of size m).
    Top-down is efficient in terms of memory usage, and it's a simpler process to describe to others, or to implement.
    The main point being, that it is simple by comparison, and for a beginner that probably matters more than speed.
    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"

  12. #12
    Registered User
    Join Date
    Apr 2013
    Posts
    1,160
    Quote Originally Posted by iMalc View Post
    Top-down (merge sort) is efficient in terms of memory usage
    Top down merge sort requires more memory, since it creates a dynamic tree structure (indexes or pointers or ...) for all the split up lists on the stack, while a bottom up merge takes about 10 variables. Both methods have the same amount of overhead for temp buffering of sorted data (or temp buffering of sorted indexes or pointers).

    Quote Originally Posted by iMalc View Post
    it's a simpler process to describe to others, or to implement.
    As posted above, all that is accomplished during the recursive phase of a top down merge sort is recursively splitting of lists until lists of size 1 are produced, and only then does any actual merging take place.

    The key concept of a merge sort is to repeatedly combine sorted lists by merging them together until a single list is produced, and this is the same for both top down or bottom up.

    If I'm trying to explain bottom up merge sort using 8 numbered cards, the initial state is 8 groups of 1 card each, and the 8 groups of size 1 are merged in pairs to create 4 groups of size 2, which are then merged to form 2 groups of size 4, which are then merged to create 1 group of size 8.

    If I explain the top down approach, I have to start with 1 group of 8 cards, split it to create 2 groups of 4 cards, split those to create 4 groups of 2 cards, and split those to create 8 groups of 1 card, just to get to the bottom up method's initial state.

    In my opinion, the main purpose of top down merge sort is as a learning tool used to teach recursion, similar to implementing factorial or fibonacci via recursion. It's not efficient, but it's useful for teaching recursion.

    There hasn't been any activity from the original poster, and perhaps he's happy with the insertion sort for the list and doesn't plan to do any further enhancements to his program, so maybe the last part of this thread should go into a separate thread about top down versus bottom up merge sort.
    Last edited by rcgldr; 08-14-2013 at 04:36 AM.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Quote Originally Posted by rcgldr View Post
    Top down merge sort requires more memory, since it creates a dynamic tree structure (indexes or pointers or ...) for all the split up lists on the stack, while a bottom up merge takes about 10 variables. Both methods have the same amount of overhead for temp buffering of sorted data (or temp buffering of sorted indexes or pointers).
    Completely false.
    There is no dynamic tree structure to create, I don't know where you got that from.
    The only memory it takes up is stack space, just a small constant amount per stack frame, with the maximum depth of stack frames being relative to the log of the total number of items in the list.
    O(log n) memory usage beats O(n) memory usage.

    Check out my implementation here: List Sorting
    loserone+_+ likes this.
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 10
    Last Post: 01-29-2013, 08:47 PM
  2. Replies: 5
    Last Post: 04-01-2010, 02:36 PM
  3. Highest and lowest value
    By manolo in forum C Programming
    Replies: 1
    Last Post: 01-23-2010, 09:57 AM
  4. Trying to sort numbers from lowest to highest
    By jw232 in forum C++ Programming
    Replies: 21
    Last Post: 01-21-2008, 03:03 PM
  5. Sort strings in double linked list. (Optimize code)
    By netstar in forum C++ Programming
    Replies: 15
    Last Post: 02-28-2005, 12:40 AM

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