Insertion Sort

Remarks

When we analyze the performance of the sorting algorithm, we interest primarily on the number of comparison and exchange.

Average Exchange

Let En be the total average number of exchange to sort array of N element. E1 = 0 (we do not need any exchange for array with one element). The average number of exchange to sort N element array is the sum of average number of number of exchange to sort N-1 element array with the average exchange to insert the last element into N-1 element array.

enter image description here

Simplify the summation (arithmetic series)

enter image description here

Expands the term

enter image description here

Simplify the summation again (arithmetic series)

enter image description here

Average Comparison

Let Cn be the total average number of comparison to sort array of N element. C1 = 0 (we do not need any comparison on one element array). The average number of comparison to sort N element array is the sum of average number of number of comparison to sort N-1 element array with the average comparison to insert the last element into N-1 element array. If last element is largest element, we need only one comparison, if the last element is the second smallest element, we need N-1 comparison. However, if last element is the smallest element, we do not need N comparison. We still only need N-1 comparison. That is why we remove 1/N in below equation.

enter image description here

Simplify the summation (arithmetic series)

enter image description here

Expand the term

enter image description here

Simplify the summation again (arithmetic series and harmonic number)

enter image description here

Algorithm Basics

Insertion sort is a very simple, stable, in-place sorting algorithm. It performs well on small sequences but it is much less efficient on large lists. At every step, the algorithms considers the i-th element of the given sequence, moving it to the left until it is in the correct position.

Graphical Illustration

Insertion Sort

Pseudocode

for j = 1 to length(A)
    n = A[j]
    i = j - 1
    while j > 0 and A[i] > n
        A[i + 1] = A[i]
        i = i - 1
    A[i + 1] = n

Example

Consider the following list of integers:

[5, 2, 4, 6, 1, 3]

The algorithm will perform the following steps:

  1. [5, 2, 4, 6, 1, 3]
  2. [2, 5, 4, 6, 1, 3]
  3. [2, 4, 5, 6, 1, 3]
  4. [2, 4, 5, 6, 1, 3]
  5. [1, 2, 4, 5, 6, 3]
  6. [1, 2, 3, 4, 5, 6]

C# Implementation

public class InsertionSort
{
    public static void SortInsertion(int[] input, int n)
    {
        for (int i = 0; i < n; i++)
        {
            int x = input[i];
            int j = i - 1;
            while (j >= 0 && input[j] > x)
            {
                input[j + 1] = input[j];
                j = j - 1;
            }
            input[j + 1] = x;
        }
    }

    public static int[] Main(int[] input)
    {
        SortInsertion(input, input.Length);
        return input;
    }
}

Auxiliary Space: O(1)
Time Complexity: O(n)

Haskell Implementation

insertSort :: Ord a => [a] -> [a]
insertSort [] = []
insertSort (x:xs) = insert x (insertSort xs)

insert :: Ord a => a-> [a] -> [a]
insert n [] = [n]
insert n (x:xs) | n <= x    = (n:x:xs)
                | otherwise = x:insert n xs


2016-08-31
2016-10-22
algorithm Pedia
Icon