Sorting of Linked List in Increasing Order

Today we will be discussing how to sorting of linked list in increasing order. But if you are unfamiliar with linked list then refer to this link where I have explained you about linked list from basic to advance. Suppose we have a linked list 4->2->5->8->1 then after sorting it should look like 1->2->4->5->8. So, let's discuss the procedure to solve the problem.

Procedure

1. First we will make a linked list.

2. Now we have many sorting algorithms like bubble sort, insertion sort, selection sort etc. We will be using bubble sort for sorting our list.

3. Now I hope you guys know how bubble sort works in arrays. If you do not know then refer to this link .

4. We will use bubble to sort linked list in the similar way we use it to sort an array.

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 sort()
    {
        struct node* temp=head;

        while(temp->next!=NULL)
        {
            struct node* temp1=temp->next;
            while(temp1!=NULL)
            {
                if(temp->data > temp1->data)
                {
                    swap(temp->data,temp1->data);
                }
                temp1=temp1->next;
            }
            temp=temp->next;
        }
    }


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

int main()
{
    linked l;
    l.insert(2);
    l.insert(5);
    l.insert(21);
    l.insert(46);
    l.insert(48);
    l.insert(54);
    l.insert(10);
    l.insert(6);
    l.insert(18);
    l.insert(-84);
    l.insert(90);
    l.insert(42);
    l.insert(81);
    l.insert(34);
    l.insert(-101);
    l.insert(6);
    l.insert(48);
    l.insert(54);
    l.insert(5);
    l.insert(-6);
    l.insert(8);
    l.insert(-54);
    l.insert(10);

    l.disp();
    l.sort();
    l.disp();
    return 0;
}

Explanation of Code

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

- insert() - which will insert elements in the linked list.
- disp() - which will display the linked list.

2. Insert some values in the linked list.
3. Now we have created a function named sort() for sorting of linked list in increasing order.
4. Then we have created 'temp' which is a pointer to node. It is initialized to head .
5. Now we have started a while loop for iterating the list. Remember we are iterating from first node till the second last node.
   while(temp->next!=NULL)
6. Then we have created a new 'temp1' which is another pointer to node. It is initialized to temp->next which means it will always point to the next node of temp .
  struct node* temp1=temp->next;
7. Now we are starting another loop from temp1 till the last node.
  while(temp1!=NULL)

SEE ALSO : The Ultimate Guide To Best Sorting Algorithms With Programs

8. Then we are comparing the data of 2 nodes adjacent to each other. If data of previous node is greater than the data of node ahead of it the we will swap the 2 nodes.
if(temp->data > temp1->data)
{
swap(temp->data,temp1->data);
}
9. Then we have incremented temp1 so that it can point to a new node.
temp1=temp1->next;
10. This loop will run until a node comes to its original position in a sorted list.
11. Then outside this loop we have incremented temp.
temp=temp->next;

See Also : Interesting facts about C Programming

If you guys want me to sort linked list using some other sorting algorithm then please comment below.

Sorting of Linked List in Increasing Order

Procedure

Code

Explanation of Code

2 Comments

Contact Form