Write a Program in C to sort a linked list containing numbers using any sorting technique of your choice.

Write a Program in C to sort a linked list containing numbers using any sorting technique of your choice.

DATA STRUCTURE DEFINITION

_______________________________________________

NODE: Data {To store data  in  the Node}

                                                      Next {To store link of  the next Node}

                ______________________________________________________________

Sorting of singly linked list Algorithm: https://browncodeit.blogspot.com/2020/06/an-algorithm-for-singly-linked-list-sorting.html

Coding in C

Source Code:

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
 
//Definition of the data structure
struct node
{
  //parts of node
 int data;
 struct node *next;
};
 
//Rename of the data structure
typedef struct node node;
 
//Function prototype declarations
node *createlist (node *head);
node *sort(node *head);
void display(node *head);
int main()
{
   //Declaration of variable
  int c;
    node *head;
    //Allocation memory dynamically for the variable
    head = (node *)malloc(sizeof(node));
    do
      {
        //Displaying and calling the functions
        printf("\nCreation of a Linked List");
        head = createlist(head);
        printf("\nContents of Linked List :\n");
        display(head); 
        printf("\nSorting of Linked List :\n");
        head = sort(head);
        printf("\n Do you want to continue ? press 1 : ");
        scanf("%d",&c);
      }while(c==1);
        getch();
}
 
       //Function to create a linked list
node *createlist (node *head)
{
   //Declaration of variables
   int n, i;
   node *list;
   //Input total number
   printf("\nEnter total number of elements in the list : ");
   scanf("%d",&n);
   //Initioalizing the list by head pointer
   list = head;
   for( i = 0; i<n; i++)
      {
        printf("Enter data :");
        scanf("%d", &list->data);
           if( i == n-1)
               list->next = NULL;
           else 
             {                                 
               list->next=(node *)malloc(sizeof(node));
               list = list->next;               
             }
       }
        return head;
}
 
//Function to display a linked list
void display (node *head)
{
   //Declaration of variables
    node *list;
    //Initializing the list by pointer head
    list= head;
    while(list->next != NULL)
    {
               printf("%d ->",list->data);
               list = list -> next;
     }
     printf("%d\n",list->data);
 }

 //Funtion to sort a linked list
  node *sort(node *head)
  {
    //Declaration of Variables
   int temp;
   node *x,*y;
   for(x=head;x!=NULL;x=x->next)
    {
      for(y=x->next;y!=NULL;y=y->next)
         {
           if(x->data>y->data)
              {
               temp = x->data;
               x->data = y->data;
               y->data = temp;
               }
         }
    }

 //Print the linked list in sorted order
 printf("\nContents of Linked List in sorted order : \n");
 display(head);
 return head;
}

Output

 Outputs:-

Creation of a Linked List

Enter total number of elements in the list : 3

Enter data :15

Enter data :12

Enter data :18

 

Contents of Linked List :

15 -> 12 -> 18

 

Sorting of Linked List :

 

Contents of Linked List in sorted order :

12 -> 15 -> 18

 

 Do you want to continue ? press 1 : 1

 

Creation of a Linked List

Enter total number of elements in the list : 4

Enter data :66

Enter data :55

Enter data :

44

Enter data :77

 

Contents of Linked List :

66 -> 55 -> 44 -> 77

 

Sorting of Linked List :

 

Contents of Linked List in sorted order :

44 -> 55 -> 66 -> 77