Algorithms - Insertion Sort

Insertion sort is a very simple sorting algorithm that is relatively efficient for small lists and mostly-sorted lists.

It is often used as part of more sophisticated algorithms. It does sort by taking elements from the list one by one and inserting them in their correct position into a new sorted list. In arrays, the new list and the remaining elements can share the array's space, but insertion is expensive, requiring shifting all following elements over by one. The insertion sort works just like its name suggests - it inserts each item into its proper place in the final list.

1. Insertion sort takes advantage of presorting.
   More efficient in practice than most other simple quadratic (O(n2)) algorithms such as selection sort or bubble sort
   the best case (nearly sorted input) is O(n).
2. Efficient for small data sets.
3. It requires fewer comparisons compared with bubble sort unless its list is backward.
   the time complexity is O(n + d), where d is the number of inversions.
4. It requires only one comparison per element for a presorted list.
5. It is stable sort. It does not change the relative order of elements with equal keys.
6. It is in-place sorting. It only requires a constant amount O(1) of additional memory space.
7. It is online sorting. It can sort a list as it receives it.
8. With a sorted array, we can insert new elements.
9. It is similar to the way we sort card deck.

The simplest implementation of this requires two list structures - the source list and the list into which sorted items are inserted. To save memory, most implementations use an in-place sort that works by moving the current item past the already sorted items and repeatedly swapping it with the preceding item until it is in place.

Shell sort is a variant of insertion sort that is more efficient for larger lists. This method is much more efficient than the bubble sort, though it has more constraints.

Psedo code should look like this:

   for i = 1, n
   j = i
   while(j > 0 and E[j] < E[j-1])
       swap(E[j], E[j-1])
       j--

C++ code

#include <iostream>
#include <iomanip>

using namespace std;

void swap(int &x;, int &y;)
{
	int temp = x;
	x = y;
	y = temp;
}

void insertion(int a[], int sz)
{
	for(int i=1; i  < sz; i++) {
		int j = i;
		while(j > 0 && (a[j] < a[j-1])) {
			swap(a[j], a[j-1]);
			j--;
		}
		cout << endl;
		for (int k = 0; k < sz; k++) cout << setw(3) << a[k];
	}
}

int main()
{
	int a[] = { 15, 9, 8, 1, 4, 11, 7, 12, 13, 6, 5, 3, 16, 2, 10, 14};
	int size = sizeof(a)/sizeof(int);
	for (int i = 0; i < size; i++) cout << setw(3) << a[i];
	insertion(a, size);
	cout << endl;
	return 0;
}

This is the way we're sorting cards.
Start by picking up a single card to form a hand that is already sorted. For each card picked up, find the right place to insert card into the hand, thus maintaining the invariant that the cards in the hand are sorted. When we hold cards in our hand, it is easy to insert a card into its correct position because the other cards are just pushed aside a bit to accept the new card.

Output from the run:

 15  9  8  1  4 11  7 12 13  6  5  3 16  2 10 14 

  9 15  8  1  4 11  7 12 13  6  5  3 16  2 10 14 

  8  9 15  1  4 11  7 12 13  6  5  3 16  2 10 14 

  1  8  9 15  4 11  7 12 13  6  5  3 16  2 10 14 

  1  4  8  9 15 11  7 12 13  6  5  3 16  2 10 14 

  1  4  8  9 11 15  7 12 13  6  5  3 16  2 10 14 

  1  4  7  8  9 11 15 12 13  6  5  3 16  2 10 14 

  1  4  7  8  9 11 12 15 13  6  5  3 16  2 10 14 

  1  4  7  8  9 11 12 13 15  6  5  3 16  2 10 14 

  1  4  6  7  8  9 11 12 13 15  5  3 16  2 10 14 

  1  4  5  6  7  8  9 11 12 13 15  3 16  2 10 14 

  1  3  4  5  6  7  8  9 11 12 13 15 16  2 10 14 

  1  3  4  5  6  7  8  9 11 12 13 15 16  2 10 14 

  1  2  3  4  5  6  7  8  9 11 12 13 15 16 10 14 

  1  2  3  4  5  6  7  8  9 10 11 12 13 15 16 14 

  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 

Code using linked list:

#include <iostream>

using namespace std;

struct List
{
	int data;
	struct List *next;
} ;

void printList(struct List *head)
{
	struct List* ptr = head;
	while(ptr) {
		cout << ptr->data << " " ;
		ptr = ptr->next;
	}
	cout << endl;
}

struct List* createList(int a[], int sz)
{
	struct List *head = new struct List;
	struct List *current = head;
	
	for(int i = 0; i < sz; i++) {
		current->data = a[i];
		if (i == sz - 1 ) {
			current->next = NULL;
			break;
		}
		current->next = new struct List;
		current = current->next;
	}

	return head;
}

// from http://analgorithmaday.blogspot.com/2011/01/insertion-sort-with-linked-listin-place.html

struct List* insertion(struct List *head)
  {
      if(head == 0) return head;
   
      // unsorted list - from the 2nd element
      struct List *unsorted = head->next;
      while(unsorted != 0)
      {
          // take key as an element in the unsorted list.
          struct List *prev = 0;
          struct List *iter = head;
          struct List *key = unsorted;
   
          // iterate within the sorted list and find the position
          while(iter != 0)
          {
              if(iter->data < key->data)
              {
                  prev = iter;
                  iter = iter->next;
              }
               else
                  break;
          }
          unsorted = unsorted->next;
          // if reached the end of sorted list 
          if(iter == key) 
              continue;
   
          // note down the position to replace in a sorted list
          struct List *replace = iter;
   
          //move iter to end of the sorted list 
          while(iter->next != key) iter=iter->next;

		  // link to the upsorted list
          iter->next = unsorted;
   
          // delete the key and replace it in sorted list
          if(prev == 0) {
              head = key;
          } else {
                prev->next = key;
          }
          key->next = replace;
		  printList(head);
       }
       return head;
  }

int main()
{
	int a[] = { 15, 9, 8, 1, 4, 11, 7, 12, 13, 6, 5, 3, 16, 2, 10, 14};
	int size = sizeof(a)/sizeof(int);

	struct List *head = createList(a, size);
	printList(head);
	head = insertion(head);
	printList(head);
	
	cout << endl;
	return 0;
}

Q: An array contains two sub- sorted arrays. Give an in-place algorithm to sort two sub arrays.

The following code uses the insertion sorting algorithm devised in the previous section.

We have an input array a[] = 1 4 5 7 8 9 2 3 6 10 11 composed of two sorted sub-arrays. We want to sort the array in place. In the process, we need to use swap() function which does in-place swap.

#include <iostream>

using namespace std;

void swap(int &x;, int &y;)
{
	x = x ^ y;
	y = x ^ y;
	x = x ^ y;
}

void insertion(int a[], int sz)
{
	for(int i=1; i  < sz; i++) {
		int j = i;
		while(j > 0) {
			if(a[j-1] > a[j]) swap(a[j-1],a[j]);
			j--;
		}
	}
	for(int i = 1; i < sz; i++) cout << a[i] << " ";
}

int main()
{
	int a[] = { 1, 4, 5, 7, 8, 9, 2, 3, 6, 10, 11 };
	int size = sizeof(a)/sizeof(int);
	for (int i = 0; i < size; i++) cout << a[i] << " ";
	cout << "  ==> " << endl;
	insertion(a, size);
	cout << endl;
	return 0;
}

Output:

1 4 5 7 8 9 2 3 6 10 11   ==>
2 3 4 5 6 7 8 9 10 11