Sort a doubly linked list in c

Question

I want to keep the linked list in sorted order when inserting items (about 200,000 items in the list), which algorithm can you recommend? I made a simple implementation using insertion sort, but its performance is very poor (lots of CPU usage).

Thanks for your help.

I did some comparison between sorting sorting and insertion sorting, but insertion sorting seems to have better performance, I'm a little confused by this result. Can you tell me what is wrong and if there is a better algorithm?

My code (for simplicity, I omitted the node preview in the node structure):

struct node { int number; struct node *next; }; 

Sort insert:

 void insert_node(int value) { struct node *new_node = NULL; struct node *cur_node = NULL; struct node *last_node = NULL; int found; /* 1 means found a place to insert the new node in, 0 means not*/ new_node = (struct node *)malloc(sizeof(struct node *)); if(new_node == NULL) { printf("memory problem\n"); } new_node->number = value; /* If the first element */ if (head == NULL) { new_node->next = NULL; head = new_node; } else if (new_node->number < head->number) { new_node->next = head; head = new_node; } else { cur_node = head; found = 0; while (( cur_node != NULL ) && ( found == 0 )) { if( new_node->number < cur_node->number ) { found = 1; } else { last_node = cur_node; cur_node = cur_node->next; } } /* We got the right place to insert our node */ if( found == 1 ) { new_node->next = cur_node; } /* Insert at the tail of the list */ else { last_node->next = new_node; new_node->next = NULL; } } 

Combine Sort:

 /* add a node to the linked list */ struct node *addnode(int number, struct node *next) { struct node *tnode; tnode = (struct node*)malloc(sizeof(*tnode)); if(tnode != NULL) { tnode->number = number; tnode->next = next; } return tnode; } /* perform merge sort on the linked list */ struct node *merge_sort(struct node *head) { struct node *head_one; struct node *head_two; if((head == NULL) || (head->next == NULL)) return head; head_one = head; head_two = head->next; while((head_two != NULL) && (head_two->next != NULL)) { head = head->next; head_two = head->next->next; } head_two = head->next; head->next = NULL; return merge(merge_sort(head_one), merge_sort(head_two)); } /* merge the lists.. */ struct node *merge(struct node *head_one, struct node *head_two) { struct node *head_three; if(head_one == NULL) return head_two; if(head_two == NULL) return head_one; if(head_one->number < head_two->number) { head_three = head_one; head_three->next = merge(head_one->next, head_two); } else { head_three = head_two; head_three->next = merge(head_one, head_two->next); } return head_three; } 

Answer 1

You do not correctly implement merge sorting, which is based on the recursive division of the list into two parts, sorting and combining the result. But in your code, you really don't split the list into two halves.

Note that in the lines:

 while((head_two != NULL) && (head_two->next != NULL)) { head = head->next; head_two = head->next->next; } head_two = head->next; head->next = NULL; 

you exit the while loop when head_two reaches the end of the list: if you, for example, reach head_two->next == NULL in the loop, then you exit it with head->next->next == NULL . And when you run head_two = head->next; , you get head_two , so head_two->next == NULL , which is the last item in the list.

This means that you are mainly doing insert sort, not merge sort.

Therefore, try to track the length of the list by adding the length parameter to the merge_sort function to be able to split it by 2. Here is a good explanation of the algorithm in wikipedia .

Answer 2

To insert items into a linked list, the precondition that it sorts does not help! There is no algorithm.

You might want to consider a different structure for your elements. Depending on your situation, a simple heap or binary search tree may serve you well.

If you want to insert many elements into a large sorted linked list, you can sort them and then perform very fast O (N) merge.

Answer 3

For an online solution (insert elements as they arrive) a balanced binary tree may be a good option. It allows you to enter (and also delete) in time O (Log (N)).

Otherwise, MergeSort can be applied to the full list.

In both cases, comparisons of O (N. Log (N)) as a whole.

Answer 4

A linked list necessarily requires O (N) steps to move to an arbitrary position in the list. Thus, it looks like this is not the right data structure for you.

You can try using a sorted set - std :: set in C ++ or SortedSet <> in C #.

If the abstraction of the sorted set does not fit your problem, perhaps the simplest data structure like a sorted linked list is a skip list: http://igoro.com/archive/skip-lists-are-fascinating/ . More complex alternatives would be AVL trees and red-black trees.

Answer 5

Priority lines (or Skip lists ) that you are looking for. They allow the use of logarithmic inserts instead of O (n) for simple linked lists.

Here's the implementation of the skip list in C on GitHub .

Answer 6

If you need to insert elements of m into a sorted list of size n , you can either directly insert complexity m·n , or pre-configure the elements (I suggest merging sorting for this) and combine them into the original list, which has complexity m·ln(m) + (n + m) .

Basically, you will use specialized versions of merge insertion and sorting, which can be implemented as online algorithms and therefore are well suited for a linked list. Keep in mind that the “tutorial” implementation of merging sort does not work well, because it does not need to iterate the list when dividing it into a sublist: you need a slightly more complex version based on the stack ...

Answer 7

you don’t really want to sort the list. Merge Sort is used to sort an unsorted list. (some of them have already indicated this).

To sort the list, you must insert each item in the desired position. so basically you should:

• find a place to enter a new entry
• insert it

The difficulty here is the search algorithm.

Thus, a binary tree or even the best AVL tree (http://en.wikipedia.org/wiki/AVL_tree) would be very efficient.

Another option is to use binary search (http://en.wikipedia.org/wiki/Binary_search_algorithm). But again, this only applies to the badge list.

Thus, in any case, you are changing the data structure or with a simple double list, O (N) complexity is the best you can achieve.

Answer 8

I made the necessary changes to your code. I tested it and it works great. Now you can close the request.

 struct node *insert_node( struct node *head, int *value ) { struct node *new_node = NULL; struct node *cur_node = NULL; struct node *last_node = NULL; int found; /* 1 means found a place to insert the new node in, 0 means not*/ new_node = (struct node *)malloc(sizeof(struct node *)); if(new_node == NULL) { printf("memory problem\n"); } new_node->number = *value; /* If the first element */ if (head == NULL) { new_node->prev = new_node->next = NULL; head = new_node; } else if (new_node->number < head->number) { new_node->next = head; head = new_node; } else { cur_node = head; found = 0; while (( cur_node != NULL ) && ( found == 0 )) { if( new_node->number < cur_node->number ) found = 1; else { last_node = cur_node; cur_node = cur_node->next; } } /* We got the right place to insert our node */ if( found == 1 ) { new_node->next = cur_node; new_node->prev = last_node; last_node->next = new_node; cur_node->prev = new_node; } /* Insert at the tail of the list */ else { last_node->next = new_node; new_node->next = NULL; new_node->prev = last_node; } } return head; } 

Answer 9

I like heaps for such things. Insert and search is O (log (n)), and bypass is O (n). The heapness property ensures that data is sorted at any time. You can move back and forth to get the benefits of a doubly linked list.