Sort a Circular Linked List

Today we will be discussing how to Sort a Circular Linked List. But if you are unfamiliar with the concepts of circular linked list then please refer to this link. Suppose we have a circular linked list like 4->3->2->1 and 1 is pointing again to 4 then the sorted list should be 1->2->3->4 . (data structures types)

Now let's discuss the procedure for sorting.

Procedure

1. First we will make a circular linked list.

2. Now we will be using bubble sort to sort the list.

3. We will be iterating from first node till the second last node. Then we making another iteration inside the first iteration itself which will traverse from the next node of the node at which the first iteration will be currently executing till the last node.

Code

#include<iostream>
using namespace std;
struct node
{
    int data;
    struct node* next;
};
struct node* head=NULL;

class linked
{

public:
    void insert(int x)
    {
        struct node* temp=new node();
        temp->data=x;
        temp->next=NULL;
        if(head==NULL)
        {
            head=temp;
        }
        else
        {
            struct node* temp1=head;
            while(temp1->next!=NULL)
            {
                temp1=temp1->next;
            }
            temp1->next=temp;

        }
    }

    void assignhead()
    {
        struct node* temp=head;
        while(temp->next!=NULL)
        {
            temp=temp->next;
        }
        temp->next=head;
    }


    void sort()
    {
        struct node* temp=head;
        while(temp->next!=head)
        {
            struct node* temp1=new node();
            temp1=temp->next;
            while(temp1!=head)
            {
                if(temp1->data<temp->data)
                {
                    swap(temp->data,temp1->data);
                }
                temp1=temp1->next;
            }
            temp=temp->next;
        }
    }

    void disp()
    {
        struct node* temp=head;
        cout<<temp->data<<" ";
        temp=temp->next;
        while(temp!=head)
        {
            cout<<temp->data<<" ";
            temp=temp->next;
        }
        cout<<endl;
    }
};

int main()
{
    linked l;
    l.insert(3);
    l.insert(5);
    l.insert(8);
    l.insert(1);
    l.insert(-2);
    l.insert(7);
    l.insert(-3);
    l.insert(11);
    l.insert(0);
    l.insert(6);
    l.assignhead();
    l.disp();
    l.sort();
    l.disp();
    return 0;
}

Explanation of code

1. First we will write a simple code of circular linked list which will have 3 functions:

- insert() - which will insert elements in the circular linked list.
- assignhead() - to make a link between last and first node.
- disp() - which will display the circular linked list.

2. Insert some values in the circular linked list.

3. Now we have created a function named sort() to sort the circular linked list.

4. Then we have made a pointer to node "temp" which is assigned to head.

struct node* temp=head;

5. Then we have started a while loop which will iterate from temp which is at head until it reaches the second last node. The loop will stop when temp's next pointer will be pointing to head and only last node will point to the head so the loop will execute until second last node because temp->next will be equal to head for the last node.

while(temp->next!=head)
{

....

}

6. Inside the while loop we have made another pointer to node called "temp1" . Then we have made temp1 to point to the next node of the temp. Each time when temp will be incremented then temp1 will always point to the next node of temp. (data structures types)

struct node* temp1=new node();
temp1=temp->next;

7. Then we have started the a while loop which will iterate temp1 till the last node.

while(temp1!=head)
{

...

}

8. Then we have checked the if condition if the data of temp will be greater then temp1 the we will swap the data .

if(temp1->data<temp->data)
{
swap(temp->data,temp1->data);
}

9. Then we have incremented temp1.

temp1=temp1->next;

10. At last we have incremented temp.

temp=temp->next;

(data structures types)

Sort a Circular Linked List

Procedure

Code

Explanation of code

Contact Form