Horje

Algorithm - Insertion Sort
Start
  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
  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 (opens new window)

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)

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 (opens new window)

Simplify the summation (arithmetic series)

enter image description here (opens new window)

Expands the term

enter image description here (opens new window)

Simplify the summation again (arithmetic series)

enter image description here (opens new window)

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 (opens new window)

Simplify the summation (arithmetic series)

enter image description here (opens new window)

Expand the term

enter image description here (opens new window)

Simplify the summation again (arithmetic series and harmonic number)

enter image description here (opens new window)

 

Read Article
https://develop.horje.com/learn/1434/reference

 

Horje