Thread: 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.

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...

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

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)