Sort Linked List
Author
shabbir ( Go4Expert Founder )
Shabbir is a developer in the field of Applications, web as well as database designing and is devoted to the optimization and usability of the code. He maintains Programming forum and is a C++ addict.
Recent Articles
- Vectors in C++, Started by blitzcoder in C-C++
- Making a screensaver in C++, Started by blitzcoder in C-C++
- Detecting errors using CRC-32 (for IEEE802.3) code, Started by blitzcoder in C-C++
- Get BGI Graphics To Work In Dev-Cpp, Started by blitzcoder in C-C++
- Find roots of any linear algebraic nth order equation by Regula Falsi method, Started by coderzone in C-C++
Similar Articles
- Basic operations in Linked List, Started by shabbir in C-C++
- Huffman Encoding in C (Minimum Variance Encoding), Started by rai_gandalf in C-C++
- Doubly Linked List Implementation in C#, Started by Sanskruti in C#
Basic operations in Linked ListI thought why not also have the one which sorts the linked list as well. I did not submit it because I thought the above list is sufficient for sorting as well but because of lots of query regarding the same I thought lets have it online as well.
Swap two nodes of a linked list
Move forward a node in linked list
Insert a node in a linked list
Double linked list
Double circular linked list
Circular linked list
Priority Queue implementation using Linked List
Queue implementation through linked list
Note: I had a major bug pointed out by RiOrius and is rectified now. Thanks for letting me know about it.
Code: Cpp
#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();
}
Linear Mode
