List insertion sort

List insertion sort

Procedure:

q  In this procedure, The elements are sorted in a linked list and must be in sorted order. Procedure starts with an empty list (or) the elements with sorted order.

q  Here, a new element can be inserted into its appropriate position with O(1) time uses insertion sort comparison procedure.

            Algorithm:

        Struct Node *newNode;

        newNode=(struct Node *)malloc(sizeof(struct Node));

        newNode->data=value;         

        struct Node *temp=head;

        Repeat   temp!=NULL

               if  (temp-> next == NULL) || (newNode->data <  temp-> next ->data) then

              begin

                    newNode-> next = temp->link;

                    temp->next = newNode;

                    break;

              end if

                    temp=temp->next;

        End Repeat

Example:

Share on Google Plus