Need help with sorting a linked list?

I have this code:

Code:

typedef struct _node{
    double total;
    struct _node *next;
    struct _node *prev;
} NODE;

NODE delete_current(NODE *current)
{
    current->prev->next = current->next;
    current->next->prev = current->prev;
    free(current);
}

NODE sort(NODE *new_list, NODE *old_list)
{
    NODE *current = (NODE *)malloc(sizeof(NODE));
    NODE *max = (NODE *)malloc(sizeof(NODE));

    while(old_list != NULL)
    {
        max = old_list->next;
        for(current = old_list->next; current != old_list; old_list= old_list->next)
        {

            if(max->total < old_list->total)
            {
                max = old_list;
            }

        }
        new_list = new_list->next;
        new_list = (NODE *)malloc(sizeof(NODE));
        new_list->total = max->total;
        delete_current(old_list);

    }
}

NODE add(NODE *sent, double i)
{
    NODE *new_node;
    new_node = (NODE *)malloc(sizeof(NODE));
    sent->prev->next = new_node;
    new_node->prev = sent->prev;
    new_node->next = sent;
    sent->prev = new_node;
    new_node->total = i;



}

NODE print_list(NODE *list)
{
    NODE *current;
    for(current = list->next; current != list; current = current->next){
        printf("%lf\n",current->total);
    }
}
int main(int argc, char **argv)
{
    NODE *new_list = (NODE *)malloc(sizeof(NODE));
    NODE *old_list = (NODE *)malloc(sizeof(NODE));
    double i;

    old_list->next = old_list;
    old_list->prev = old_list;

    for( i =1; i<=10 ; i++)
    {
        add(old_list, i);

    }
    print_list(old_list);

    sort(new_list, old_list);

    print_list(new_list);
}

Im having trouble on my sort() function.. I know print_list works and add works..
The whole for loop setting the total in each node is just me making a test list.. its not my actual list.. The sort function is supposed to be sorting the list from greatest to least.

You could:

• build an array of nodes
• outsource sorting to qsort
• relink your list

This works well especially if the list is under a hundred or so nodes. If you must build your own sort procedure, then I would suggest an attempt at merge sort.

A sort routine for a list should never need to allocate any nodes. All it needs to do is change what various nodes point to. Definitely don't malloc for max and current, just assign them NULL to begin with. Then instead of using malloc right before you delete a node, simply reuse the same node, i'e' instead of copying total, just change the pointers.

As an added bonus, I'll post some of my C++ selection sort code for a doubly-linked ring-list (which I believe is exactly the structure you are using):

Code:

template <class TItem>
void SelectionSort(TItem *&head) {
	TItem *unsortedhead = head, *curr;
	TItem *lowhead = NULL, *currlow;
	while (unsortedhead != NULL) {
		currlow = curr = unsortedhead;
		//step through list finding lowest item
		do {
			if (*curr < *currlow)
				currlow = curr;
			curr = curr->next;
		} while (curr != unsortedhead);
		//take the item out of the list
		Remove(unsortedhead, currlow);
		//append the item to the end of the new list
		Put(lowhead, currlow);
	}
	//put new list back into old list
	head = lowhead;
}

Originally Posted by iMalc

A sort routine for a list should never need to allocate any nodes. All it needs to do is change what various nodes point to. Definitely don't malloc for max and current, just assign them NULL to begin with. Then instead of using malloc right before you delete a node, simply reuse the same node, i'e' instead of copying total, just change the pointers.

As an added bonus, I'll post some of my C++ selection sort code for a doubly-linked ring-list (which I believe is exactly the structure you are using):

Code:

template <class TItem>
void SelectionSort(TItem *&head) {
	TItem *unsortedhead = head, *curr;
	TItem *lowhead = NULL, *currlow;
	while (unsortedhead != NULL) {
		currlow = curr = unsortedhead;
		//step through list finding lowest item
		do {
			if (*curr < *currlow)
				currlow = curr;
			curr = curr->next;
		} while (curr != unsortedhead);
		//take the item out of the list
		Remove(unsortedhead, currlow);
		//append the item to the end of the new list
		Put(lowhead, currlow);
	}
	//put new list back into old list
	head = lowhead;
}

I tried to turn your code into something that would work for my program..

Code:

NODE delete_current(NODE *current)
{
    current->prev->next = current->next;
    current->next->prev = current->prev;
    free(current);
}

NODE new_list_add(NODE *sent, NODE *high)
{
    NODE *new_node;
    new_node = (NODE *)malloc(sizeof(NODE));
    sent->prev->next = new_node;
    new_node->prev = sent->prev;
    new_node->next = sent;
    sent->prev = new_node;
    new_node->total = high->total;
}

NODE sort(NODE *head)
{
    NODE *unsorted = head;
    NODE *current;
    NODE *high_head;
    NODE *current_high;

    high_head->prev = high_head;
    high_head->next = high_head;

    while(unsorted != NULL)
    {
        current_high = current = unsorted;
        current = current->next;
        while(current != unsorted)
        {
            if(current->total > current_high->total)
            {
                current_high = current;
            }
            current = current->next;
        }

        delete_current(unsorted);
        new_list_add(high_head, current_high);  //<<error


    }

}

its saying I have a "previous implicit declaration of ânew_list_addâ was here"

I dont know what to do...pleaseeee help me...

I just noticed that you're returning NODE from your functions. You shouldn't do that. They either need to return NODE* or they should return NULL.

No idea why you would get that error/warning?

Code:

    NODE *unsorted = head;
    NODE *current;
    NODE *high_head;
    NODE *current_high;

    high_head->prev = high_head;
    high_head->next = high_head;

At this point in your code "high_head" seems to be undefined. So, the next and prev links would also be undefined. It looks as if this could screw things up when you call new_list_add(). Or, at least thats the impression I get. Doubt its why you get that error tho, should get a segfualt instead.

Originally Posted by mike_g

Code:

    NODE *unsorted = head;
    NODE *current;
    NODE *high_head;
    NODE *current_high;

    high_head->prev = high_head;
    high_head->next = high_head;

At this point in your code "high_head" seems to be undefined. So, the next and prev links would also be undefined. It looks as if this could screw things up when you call new_list_add(). Or, at least thats the impression I get. Doubt its why you get that error tho, should get a segfualt instead.

Ok I malloced high_head.. and that fixed the error .. but now im in an infinite loop? help ?

Code:

NODE delete_current(NODE *current)
{
    current->prev->next = current->next;
    current->next->prev = current->prev;
    free(current);
}

NODE new_list_add(NODE *sent, NODE *high)
{
    NODE *new_node;
    new_node = (NODE *)malloc(sizeof(NODE));
    sent->prev->next = new_node;
    new_node->prev = sent->prev;
    new_node->next = sent;
    sent->prev = new_node;
    new_node->total = high->total;
}

NODE sort(NODE *head)
{
    NODE *unsorted = head;
    NODE *current;
    NODE *high_head;
    NODE *current_high;

    high_head = (NODE *)malloc(sizeof(NODE));

    high_head->prev = high_head;
    high_head->next = high_head;

    while(unsorted != NULL)
    {
        current_high = current = unsorted;
        current = current->next;
        while(current != unsorted)
        {
            if(current->total > current_high->total)
            {
                current_high = current;
            }
            current = current->next;
        }

        new_list_add(high_head, current_high);
        delete_current(current_high);
    }

}

But what exactly is the new node you have malloced doing?

You should not have to create any new nodes in order to sort your list; you just need to change where the links point to.

In pseudo code what (I think) you want to be doing is:
[code]Set the head node of the new (sorted) list to NULL

While there are nodes on the old (unsorted) list
Loop through each node on the unsorted list

Originally Posted by mike_g

But what exactly is the new node you have malloced doing?

You should not have to create any new nodes in order to sort your list; you just need to change where the links point to.

In pseudo code what (I think) you want to be doing is:
[code]Set the head node of the new (sorted) list to NULL

While there are nodes on the old (unsorted) list
Loop through each node on the unsorted list

Its holding the new list.. I dont know how to do what youre saying "change where they point to"

here is my whole code.. i changed set new_list to equal my high_head..

Code:

NODE delete_current(NODE *current)
{
    current->prev->next = current->next;
    current->next->prev = current->prev;
    free(current);
}

NODE new_list_add(NODE *sent, NODE *high)
{
    NODE *new_node;
    new_node = (NODE *)malloc(sizeof(NODE));
    sent->prev->next = new_node;
    new_node->prev = sent->prev;
    new_node->next = sent;
    sent->prev = new_node;
    new_node->total = high->total;
}

NODE sort(NODE *new_list, NODE *head)
{
    NODE *unsorted = head;
    NODE *current;
    NODE *high_head;
    NODE *current_high;

    high_head = (NODE *)malloc(sizeof(NODE));

    high_head->prev = high_head;
    high_head->next = high_head;

    while(unsorted != NULL)
    {
        current_high = current = unsorted;
        current = current->next;
        while(current != unsorted)
        {
            if(current->total > current_high->total)
            {
                current_high = current;
            }
            current = current->next;
        }

        new_list_add(high_head, current_high);
        delete_current(current_high);
    }
new_list = high_head;
}

NODE add(NODE *sent, double i)
{
    NODE *new_node;
    new_node = (NODE *)malloc(sizeof(NODE));
    sent->prev->next = new_node;
    new_node->prev = sent->prev;
    new_node->next = sent;
    sent->prev = new_node;
    new_node->total = i;

}
NODE print_list(NODE *list)
{
    NODE *current;
    for(current = list->next; current != list; current = current->next){
        printf("%lf\n",current->total);
    }
}


int main(int argc, char **argv)
{
    NODE *new_list = (NODE *)malloc(sizeof(NODE));
    NODE *old_list = (NODE *)malloc(sizeof(NODE));
    double i;

    old_list->next = old_list;
    old_list->prev = old_list;

    for( i =1; i<=10 ; i++)
    {
        add(old_list, i);

    }
    print_list(old_list);

    sort(new_list, old_list);

    print_list(new_list);
    return 0;
}

But what are you trying to achieve by mallocing a new node here?

The first node on your sorted list (high_head) should be set to NULL, so that it acts as the terminator.

<edit> oh, and get rid of this part:

Code:

    high_head->prev = high_head;
    high_head->next = high_head;

</edit>

Now, assuming that your add and delete functions are fine I think this should work.

Another approach would be to simply relink you list. This would avoid all the adding and deleting. Basically you do not have to create any new nodes to sort your list; its simply a matter of changing where the links point to. to give you an idea of how you could go about it in pseudo code:

Code:

Set the head of the new (sorted)  list to NULL
  
While there are nodes on the old (unsorted) list
    Loop through each node on unsorted list
        Store the node before the smallest result
        Store the smallest result
        Store the node after the smallest result

    Link node from before smallest result to node after smallest result
    Link node from after smallest result to node before smallest result
   
    Add orphaned smallest result node to the new (sorted) list

but, considering where you are its probably easiest to try and get what you have to work.

Edit2: oh, and ignore my last post above; it was an accident.

Originally Posted by mike_g

But what are you trying to achieve by mallocing a new node here?

The first node on your sorted list (high_head) should be set to NULL, so that it acts as the terminator.

<edit> oh, and get rid of this part:

Code:

    high_head->prev = high_head;
    high_head->next = high_head;

</edit>

Now, assuming that your add and delete functions are fine I think this should work.

Another approach would be to simply relink you list. This would avoid all the adding and deleting. Basically you do not have to create any new nodes to sort your list; its simply a matter of changing where the links point to. to give you an idea of how you could go about it in pseudo code:

Code:

Set the head of the new (sorted)  list to NULL
  
While there are nodes on the old (unsorted) list
    Loop through each node on unsorted list
        Store the node before the smallest result
        Store the smallest result
        Store the node after the smallest result

    Link node from before smallest result to node after smallest result
    Link node from after smallest result to node before smallest result
   
    Add orphaned smallest result node to the new (sorted) list

but, considering where you are its probably easiest to try and get what you have to work.

Edit2: oh, and ignore my last post above; it was an accident.

Ok is this right?

Code:

NODE sort(NODE *head)
{
    NODE *unsorted = head;
    NODE *current;
    NODE *high_head;
    NODE *current_high;
    NODE *before_high;
    NODE *after_high;

    high_head = NULL;

    unsorted = unsorted->next;
    while(unsorted != NULL)
    {
        current_high = current = unsorted;
        for(current=unsorted->next; current != unsorted; current=current->next)
        {
            if(current->total > current_high->total)
            {
                before_high = current->prev;
                current_high = current;
                after_high = current->next;
            }
            current = current->next;
        }
        before_high->next = after_high;
        after_high->prev = before_high;


        new_list_add(high_head, current_high);
        delete_current(current_high);
    }
    head = high_head;

}

Ok is this right?

No, sorry, it looks as if I got you confused. The second part of my post mentioned a different method of sorting the list. Not something you should add to the code you have.

Just do something like:

Code:

NODE* sort(NODE *new_list, NODE *head) /* funtion returns pointer to the sorted head */
{
    NODE *unsorted = head;  /* head of unsorted list */
    NODE *current;
    NODE *high_head = NULL; /* head of sorted list */
    NODE *current_high;

    while(unsorted != NULL)
    {
        current_high = current = unsorted;
        current = current->next;
        while(current != unsorted)
        {
            if(current->total > current_high->total)
            {
                current_high = current;
            }
            current = current->next;
        }

        new_list_add(high_head, current_high);
        delete_current(current_high);
    }
    return high_head; 
}

Does that work for you?

Originally Posted by mike_g

No, sorry, it looks as if I got you confused. The second part of my post mentioned a different method of sorting the list. Not something you should add to the code you have.

Just do something like:

Code:

NODE* sort(NODE *new_list, NODE *head) /* funtion returns pointer to the sorted head */
{
    NODE *unsorted = head;  /* head of unsorted list */
    NODE *current;
    NODE *high_head = NULL; /* head of sorted list */
    NODE *current_high;

    while(unsorted != NULL)
    {
        current_high = current = unsorted;
        current = current->next;
        while(current != unsorted)
        {
            if(current->total > current_high->total)
            {
                current_high = current;
            }
            current = current->next;
        }

        new_list_add(high_head, current_high);
        delete_current(current_high);
    }
    return high_head; 
}

Does that work for you?

im getting a seg fault in the sort function and in the new_list_add function

Ok, you have problems with you add function as well.

If this is what you have:

Code:

NODE new_list_add(NODE *sent, NODE *high)
{
    NODE *new_node;
    new_node = (NODE *)malloc(sizeof(NODE));
    sent->prev->next = new_node;
    new_node->prev = sent->prev;
    new_node->next = sent;
    sent->prev = new_node;
    new_node->total = high->total;
}

Firstly, you want to be returning a pointer to your new_node, not a NODE struct.

Next, you need to figure out whats linking to where.
"sent" would be the head of your sorted list.
"high" would be the node to add.
So, "sent->next" should point to new_node and "new_node->prev" should point to "sent"

since you have a doubly linked list "new_node->next" should be set to NULL to terminate the list.

Once you have created your new node, you should return the pointer to it as it will be the new head of your list.

I think you want something like:

Code:

NODE* new_list_add(NODE *sent, NODE *high)
{
    NODE *new_node;
    new_node = (NODE *)malloc(sizeof(NODE));
    sent->next = new_node;
    new_node->prev = sent;
    new_node->next = NULL;
    new_node->total = high->total;
    return new_node;
}

On a side note, in relation to delete_current, it should probably be declared void as it does not return anything. IE:

Code:

void delete_current(NODE *current)

Okay, I avoided posting my definition of Remove and Put, so that you could finish it on your own (hopefully). I'll describe what they need to do though.
Firstly though, You need to remove the node from the unsorted list before you add it to the sorted list. Again I will stress that this should be done entirely without any call to malloc during the whole time the sorting happens.
So, you remove the node from the unsorted list list, and then you add it to the sorted list.
Removing the node from the unsorted list generally involves finding its neighbours and setting them to point to each other instead of to the node you are removing. You also need to handle the special case of removing from the head of the list, which is why I passed in the pointer to the head of the unsorted list, so it could be updated when required.
Putting the node in the sorted list involves Getting the node prior to the head node (which is actually the last node) and modifying one he pointers from each of those nodes to point to the node being inserted, AND you have to change both pointers in the new node to point back at the other two.

mike_g: You need to understand one thing about what he is coding. In this list, the last node points back to the first node, not to NULL. In other words it is a ring-list. You can confirm this by looking at his print_list function.

However, I now notice that he is using a sentinel as the first item in the list. You have made the necessary change for this above what I posted, already. Actually perhaps he will want to use malloc once afterall, to create the sentinel for the sorted list. Don't forget to free it!