Question about sorting and linked lists

Blackened Justice · 12-14-2011, 06:52 PM

Hey everyone. I'm working on a part of my programming project. Basically, I read data from a file, a list of airplanes and their properties: position, destination, where they come from, heading, etc., another file containing the properties of the arrival and departure gates and the runways. Then I must list the airplanes by destination, for those that have the same destination, by altitude, and for those that have the same destination and altitude, by distance to their destination.

Now, I'm having some trouble tackling this problem. I'm using a singly linked list, without sentinel nodes. I'm thinking whether I should insert the airplanes already in that order, or just insert them in the beginning/end of the list, and then find some way to print them out as described above. Does anyone have any suggestion?

firstfire · 12-15-2011, 12:38 AM

Quote:

Originally Posted by Blackened Justice

Now, I'm having some trouble tackling this problem. I'm using a singly linked list, without sentinel nodes. I'm thinking whether I should insert the airplanes already in that order, or just insert them in the beginning/end of the list, and then find some way to print them out as described above. Does anyone have any suggestion?

Well, a quick but inefficient way to sort a linked list is a bubble sort, because it requires only exchanging pairs of adjacent elements. In case of singly linked list it is simpler to swap the data (or pointers to data) containing in list nodes, not the nodes itself.

You can also store your data in an array (not list) and use the `qsort()' function (assuming you program in C) to sort elements. See `man qsort' for details.

In any case you will need a function to compare two records. Here is a pseudo code:

Code:

int airplane_cmp(airplane A, airplane B)
{
    int c = strcmp(A.dest, B.dest);
    if(c) return c;   // if destinations different
    else if(A.alt != B.alt ) return (A.alt < B.alt)?  -1 : 1;  // if altitudes different
    else if(A.dist != B.dist) return (A.dist<B.dist)? -1 : 1;  // if distances different
    else return 0; // equal
}

Hope this helps.

ntubski · 12-15-2011, 12:53 PM

Quote:

Originally Posted by firstfire

Well, a quick but inefficient way to sort a linked list is a bubble sort, because it requires only exchanging pairs of adjacent elements. In case of singly linked list it is simpler to swap the data (or pointers to data) containing in list nodes, not the nodes itself.

If you want a simple but inefficient sorting algorithm try Insertion or Selection sort, bubble sort is just too bad to ever be used.

Nominal Animal · 12-15-2011, 04:42 PM

Quote:

Originally Posted by Blackened Justice

Then I must list the airplanes by destination, for those that have the same destination, by altitude, and for those that have the same destination and altitude, by distance to their destination.

Now, I'm having some trouble tackling this problem. I'm using a singly linked list, without sentinel nodes. I'm thinking whether I should insert the airplanes already in that order, or just insert them in the beginning/end of the list, and then find some way to print them out as described above. Does anyone have any suggestion?

It is usually simpler to insert the new node into the correct position, than to sort the list afterwards. Effectively, the insertion works like insertion sort (O(N²) running time). For singly linked lists, merge sort is often a good choice, and will yield O(N log N) running time.

(If you are unfamiliar with the notation, O(N²) means that doubling the size of the data will quadruple the running time. O(N log N) means that doubling the size of the data will slightly more than double the running time. O(N) means that doubling the size of the data would just double the running time. The notation does not say anything about which algorithm is faster with the same amount of data, only about how the running time changes for each algorithm when the amount of data changes.)

While insertion sort is slower than merge sort, inserting the nodes as soon as you can create them allows you to do meaningful work while still doing the I/O to obtain the data. When you have lots and lots of data, your process will be I/O bound; i.e., the CPU will be just waiting for work to do. Using insertion sort to insert the data immediately when obtained will often complete faster (wall clock time) while using more CPU time than sorting the data afterwards using a better algorithm such as merge sort, because the time used for the slower sorting would otherwise be spent waiting for I/O.

When using singly linked list without sentinels, temporary sentinels simplify the code a lot. Consider this C insertion example:

Code:

struct node {
    struct node *next;
    int          key; /* Sorted in ascending order */
    /* Other payload... */
};

/* Insert node(s) to list, and return the new list.
 * list has keys in ascending order; nodes is either a single node
 * or an unsorted list of nodes.
*/
struct node *insert_list(struct node *list, struct node *nodes)
{
    struct node  sentinel; /* Temporary sentinel node. Note: Not a pointer! */
    struct node *cursor, *newnode;

    while (nodes) {

        /* newnode is the new node to insert. */
        newnode = nodes;
        nodes = nodes->next;
        /* Note: newnode->next is considered NULL at this point. */

        /* Initialize the temporary sentinel. */
        sentinel.next = list;
        cursor = (struct node *)&sentinel;

        /* Advance, until the insert position is found.
         * The new node is inserted before cursor->next. */
        while (cursor->next && cursor->next->key < newnode->key)
            cursor = cursor->next;

        /* Insert. */
        newnode->next = cursor->next;
        cursor->next = newnode;

        /* The list root was maintained by the temporary sentinel. */
        list = sentinel.next;
    }

    return list;
}

Note that only the next pointer is used in the temporary sentinel; its key is never accessed.

sundialsvcs · 12-15-2011, 07:53 PM

I trust that this is purely an exercise ...