Sorting the link list

Here we will see how to sort the link list on the info field of its nodes.

Algorithm to sort link list:

• Set TEMP = START
• While(TEMP is not NULL)
  • Set CURRENT to point to next of TEMP, (CURRENT = TEMP->NEXT)
  • While(CURRENT is not NULL)
    • If(TEMP->INFO > CURRENT->INFO)
      • Swap(TEMP->INFO, CURRENT->INFO)
    • End If;
    • Update CURRENT to point to next node. (CURRENT = CURRENT->NEXT)
  • End While;
  • Update TEMP to point to next node, (TEMP = TEMP->NEXT)
• End While;

 

Function to sort the link list:

We will use bubble sort algorithm to sort the list. Code below:

void sortList(NODE **start){
 NODE *current, *temp;
 int tempinfo;
 temp = *start;
 while( temp ){
  current = temp->next;
  while( current ){
   if( temp->info > current->info ){
    tempinfo = temp->info;
    temp->info = current->info;
    current->info = tempinfo;
   }
   current = current->next;
  }
  temp = temp->next;
 }
}

 

Program to sort the link list:

#include <stdio.h>
#include <malloc.h>

struct node{
 int info;
 struct node *next;
};
typedef struct node NODE;

void insertAtFirst(NODE **, int);
void traverse(NODE **);
void sortList(NODE **);

int main(){
 
 NODE *start = NULL;
 
 insertAtFirst(&start, 4);
 insertAtFirst(&start, 2);
 insertAtFirst(&start, 9);
 insertAtFirst(&start, 5);
 
 printf("The node of list before sorting: ");
 traverse(&start);
 
 sortList(&start);
 
 printf("\nThe node of list after sorting: ");
 traverse(&start);
 
 return 0;
}

void sortList(NODE **start){
 NODE *current, *temp;
 int tempinfo;
 temp = *start;
 while( temp ){
  current = temp->next;
  while( current ){
   if( temp->info > current->info ){
    tempinfo = temp->info;
    temp->info = current->info;
    current->info = tempinfo;
   }
   current = current->next;
  }
  temp = temp->next;
 }
}

void insertAtFirst(NODE **start, int info){
 NODE *ptr = (NODE*) malloc(sizeof(NODE));
 ptr->info = info;
 ptr->next = *start;
 *start = ptr;
}

void traverse(NODE **start){
 NODE *temp;
 temp = *start;
 while(temp != NULL){
  printf("%d  ", temp->info);
  temp = temp->next;
 }
}

 

The node of list before sorting: 5  9  2  4
The node of list after sorting: 2  4  5  9

Related topics:

• Insert node at first position in singly link list
• Insert node at last position in singly link list
• Insert node at specific position in singly link list
• Delete node at first position in singly link list
• Delete node at last position in singly link list
• Delete node at specific position in singly link list
• Find number of nodes in singly link list
• Dublication of singly link list
• Concatenation of two singly link list
• Sorting the singly link list
• Circular Link List
• Doubly Link List
• Circular Doubly Link List