How to sort a Linked List (doubly linked, singly linked)?

Insert sort:

C++:
01 void sortDoublelyLinkedList(Node** head)
02 {
03     Node* cur=(*head)->next;
04     Node* tmp=cur->next;
05     while(cur!=NULL){
06         Node* toadd=cur;
07         if(cur->value>=cur->prv->value){
08             cur=tmp;
09             if(tmp!=NULL)
10             tmp=tmp->next;
11             continue;
12         }
13         while((toadd->value>=cur->value)&&(toadd!=(*head)))
14             toadd=toadd->prv;
15         if(cur->next!=NULL)
16             cur->next->prv=cur->prv;
17         cur->prv->next=cur->next;
18         if((toadd==(*head))&&(cur->value<(*head)->value)){
19             cur->next=(*head);
20             (*head)->prv=cur;
21             (*head)=cur;
22             cur=tmp;
23             if(tmp!=NULL)
24                 tmp=tmp->next;
25             continue;
26         }
27         else if(cur->value>=toadd->value){
28             toadd=toadd->next;
29         }
30         cur->next=toadd;
31         cur->prv=toadd->prv;
32         toadd->prv->next=cur;
33         toadd->prv=cur;
34         cur=tmp;
35         if(tmp!=NULL)
36             tmp=tmp->next;
37     }
38 }
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s