1

Insertion Sort

Definition:

Insertion sort is a type of sort that simply sort an array.

It is less efficient than quick sort, merge sort.  However, it is simply implemented and it works for small data sets.

In worst and average case its time complexity is O(n^2) (square of n), in best case,  its time complexity is O(n).

It has several advantages:

  • Stable,
  • In-place : only needs O(1) additional memory,
  • Online,
  • Simple implementation,
  • Efficient for small data sets.

How does it work? 

Insertion sort iterates and growing a sorted list. In each iteration, it takes an element from list and finds the exact location of it in the list. After that it places in the correct place, iteration goes on until list is fully sorted.  In each  iteration, an element (x) places to the right place  and list becomes sorted like example below.

Insertionsort-before

becomes

Insertionsort-after

 

In  picture below, you can see the  insertion sort example.

Insertion-sort-example-300px

Insertion Sort Example

Animation:

For better understanding, go to this animation page.

Pseudocode:

Insertion Sort ( X[ ] , n)
    for j <- 2 to n
       key <- X [ j ]
       i <- j - 1
       while i > 0 and X [ i ] > key
          X [ i + 1 ] <- X [ i ]
          i < - i -1
       X [ i + 1 ] = key


 

References:

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), “2.1: Insertion sort”, Introduction to Algorithms (second ed.), MIT Press and McGraw-Hill, pp. 15–21.

Figures from:  http://en.wikipedia.org

 

For more algorithms, go to Algorithms Section.

0

Foreword

Knowledge is a valuable product that is extracted from data after difficult processes. However, it will be bigger day by day when it is shared.

In this information age, as a human, we should increase our knowledge for man-kind.

I strongly believe that if you

Change Your World With Knowledge,

You can

Change All Over The World..

In this site, there are 4 main sections in terms of Algoritnms, Android, Java and Php & MySql.

Every section, there will be valuable knowledge and examples.

Get Knowledge,  then Share It..