Sort the content of a linked list. Note: I had a major bug pointed out by RiOrius and is rectified now. Thanks for letting me know about it. Code: #include <iostream> using namespace std; #define NULL 0 class LinkList { private: struct Node { Node* prev; int value; Node *next; }; Node *first; public : LinkList() { Node *t1 = new Node(); t1->prev = NULL; t1->value = 4; t1->next = NULL; first = t1; Node *t2 = new Node(); t2->prev = t1; t2->value = 6; t2->next = NULL; t1->next = t2; Node *t3 = new Node(); t3->prev = t2; t3->value = 1; t3->next = NULL; t2->next = t3; Node *t4 = new Node(); t4->prev = t3; t4->value = 5; t4->next = NULL; t3->next = t4; Node *t5 = new Node(); t5->prev = t4; t5->value = 8; t5->next = NULL; t4->next = t5; Node *t6 = new Node(); t6->prev = t5; t6->value = 1; t6->next = NULL; t5->next = t6; Node *t7 = new Node(); t7->prev = t6; t7->value = 0; t7->next = NULL; t6->next = t7; } ~LinkList() { Node *temp = first, *current = first; while(current != NULL) { temp = current->next; delete current; current = temp; } } void Display() { Node *temp; for(temp = first; temp != NULL; temp = temp->next) { cout<<temp->value<<" , "; } cout<<endl; } void Sort() { Node *current, *cur; for(current = first; current->next != NULL; current = current->next) { Node *minimum = current; for(cur = current ; cur != NULL; cur = cur->next) { if(minimum->value > cur->value) { minimum = cur; } } if(minimum != current) { Node *current_previous, *current_next, *min_previous, *min_next; // Initialize them current_next = current->next; min_previous = minimum->prev; min_next = minimum->next; current_previous = current->prev; if(current_previous == NULL) { // Change the First Node first = minimum; } if(current->next == minimum) { // Nodes are Adjacent minimum->prev = current_previous; minimum->next = current; current->prev = minimum; current->next = min_next; if(min_next) { min_next->prev = current; } if(current_previous) { current_previous->next = minimum; } } else { minimum->prev = current_previous; minimum->next = current_next; current->prev = min_previous; current->next = min_next; if(current_next) { current_next->prev = minimum; } if(min_previous) { min_previous->next = current; } if(min_next) { min_next->prev = current; } if(current_previous) { current_previous->next = minimum; } } current = minimum; } } } }; void main() { LinkList list; cout<<"LinkList = "; list.Display(); cout<<"\n\nSorting \n\n"; list.Sort(); cout<<"LinkList = "; list.Display(); }
Hi, The code you have written is good but according to me the sorting function should be small, its too complex.
Re: Sort Linked List(Simple coding for sorting) Code: #include<stdio.h> #include<stdlib.h> void create(); void show(); void sort(); struct node { int d; struct node *link; }*head=0,*current,*prev; int num_nodes=0; void main() { int choice; while(1) { printf("\n1.Create\n2.Display\n3.Sort\n4.Exit\n"); printf("Enter ur choice:"); scanf("%d",&choice); switch(choice) { case 1: create(); break; case 2: show(); break; case 3: sort(); break; case 4: exit(0); } } } void create() { int data; current=(struct node*)malloc(sizeof(struct node)); printf("Enter the data:"); scanf("%d",&data); num_nodes++; if(head==0) { head=current; current->d=data; current->link=NULL; prev=current; } else{ current->d=data; current->link=NULL; prev->link=current; prev=current; } } void show() { current=head; while(current!=NULL) { printf("->%d",current->d); current=current->link; } } void sort() { // current ptr is used to point the current node in the list //prev ptr is used to point the previous node of current node //next ptr is used to point the next node of current node int i,j; struct node *prev=0,*next=0; //Initially current node and previous node should be the same(first) node in the list current=head; prev=head; next=head->link; for(i=0;i<num_nodes-1;i++) { for(j=0;j<num_nodes-i-1;j++) { if(current->d>next->d) { current->link=next->link; next->link=current; if(current==head) { head=next;prev=next; } else { prev->link=next;prev=next; } if(next!=NULL)//check whether final node is reached next=current->link; } else//just moved each node ptr by one position { prev=current; current=next; next=current->link; } } //For next iteration make the initial settings again current=head; prev=head; next=current->link; } //For display the sorted numbers current=head; while(current!=NULL) { printf("->%d",current->d); current=current->link; } }
Thats a good one. Yours is a Linear sort and I have used bubble sort but I am sure with bubble sort also some code blocks can be made shorter.
Re: Sort Linked List(Simple coding for sorting) what kind of sorting method is used is it a buble sort ?
In the same way as he has done for numbers. You just need to overload > operator if you are using C++. If you are using C, then write a function that does the string comparison and tells you the result. strcmp can be used
Re: Sort Linked List(Simple coding for sorting) Hi. Your code is nice. May I ask why do you use 2 for loop in this case? Appreciate your help!
Re: Sort Linked List(Simple coding for sorting) Ya, I try to check if this value referenced by the pointer is greater than the value referenced by another pointer. But it doesn't work.
Re: Sort Linked List(Simple coding for sorting) Hi can i check with you, the reason for having 2 loop is it because you want to compare the first node with the second node and so on? Thank you!
