Insertion sort with Linked List–in-place

 

Introduction

Yesterday we saw about insertion sort using Linked list. Linked list are really interesting, if you do things the correct way. Let me explain about insertion sort using linked list in-place version which is available in most of the C++ standard libraries nowadays.

My version may be little bit complex. Please bear with me with the number of temporaries used. It could be minimized a lot!!.

Let us directly dive into the code.

Code

• head is the start of a dynamic linked list. We assume head has sorted list initially
• unsort is the start of the unsorted linked list any time in the whole code
• prev, iter is used to mark the position to insert the element in the sorted list under head.
• when iter and key comes to a same position, key lies in the end of the sorted list. So, we continue the loop
• We move iter each time to the end of the sorted list and connect it with the unsorted list. This is a very critical step and can be optimized one.

 

   1:   

   2:  List* insertion_sort_inplace(List *head)

   3:  {

   4:      if(head == 0) return head;

   5:   

   6:      // assume head is sorted

   7:      List *unsort = head->next;

   8:      while(unsort != 0)

   9:      {

  10:          // take key as an element in the unsorted list.

  11:          List *prev = 0;

  12:          List *iter = head;

  13:          List *key = unsort;

  14:   

  15:          // iterate within the sorted list and find the position

  16:          while(iter != 0)

  17:          {

  18:              if(iter->data < key->data)

  19:              {

  20:                  prev = iter;

  21:                  iter = iter->next;

  22:              }

  23:              else

  24:                  break;

  25:          }

  26:          unsort = unsort->next;

  27:          // if reached the end of sorted list, continue

  28:          if(iter == key) 

  29:              continue;

  30:   

  31:          // note down the position to place

  32:          List *place = iter;

  33:   

  34:          //move iter to end of the sorted list and connect with unsort

  35:          while(iter->next != key) iter=iter->next;

  36:          iter->next = unsort;

  37:   

  38:          // delete the key and place it in sorted list

  39:          if(prev == 0) {

  40:              head = key;

  41:          } else {

  42:              prev->next = key;

  43:          }

  44:          key->next = place;

  45:   

  46:      }

  47:      return head;

  48:  }

  49:   

  50:  void main()

  51:  {

  52:      List *head = createNode(5);

  53:      append(head, createNode(2));

  54:      append(head, createNode(7));

  55:      append(head, createNode(6));

  56:      append(head, createNode(4));

  57:      append(head, createNode(2));

  58:      append(head, createNode(10));

  59:      append(head, createNode(1));

  60:      append(head, createNode(3));

  61:   

  62:      List *sorted = insertion_sort_inplace(head);

  63:  }

 

Important points

• Note that the above algorithm doesn’t require any size input. It can process any large infinite numbers which are dynamically created.
• The important concept on computers is that, when you create something dynamically, the memory is created on the heap which is on RAM. So, this in-place version requires huge RAM space when the list is huge.
• Again and Again, Linked list cannot be accessed based on index. Address stored in temporaries plays important role. If you need to clean up temporaries, Recursion is the solution which we are afraid of currently.
• Another important demerit in the above code is, we traverse again to reach the end of the sorted list. But still it equates to O(n²).