Insertion Sort

Posted by Kyprulez in Algorithmics, Programming | 9 comments

About

Insertion sort is a sorting algorithm, that compares the entries of an array/list and builts its entries one at a time.It is a good algorithm for sorting a small number of elements.It is often compared to the process of sorting a deck of cards.Let’s see how it works.

The Sorting Problem

We have a sequence of n numbers.

and we want to get a permutation

that meets the following property :

In other words, to sort the sequence of n numbers.

Implementation

#include<iostream>
using namespace std;

void insertionSort(int a[], int n)
{
    int i, j;

    for(j = 1; j < n; j++)
    {
        int key = a[j];
        i = j - 1;

        while((i >= 0) && (a[i] > key))
        {
            a[i + 1] = a[i];
            i = i - 1;
        }

        a[i + 1] = key;
    }
}

int main()
{
    int v[] = { 5, 3, 2, 9, 4, 7, 6, 10, 1, 8 };
    int n = sizeof(v) / 4;

    insertionSort(v, n);

    for(int i = 0; i < n; i++)
    cout << v[i] << endl;

    cin >> v[0];
}

Visual representation and explanation

In the image above we see what happens for each iteration of j.j represents both the “inserted” element as well as the one that we use to compare with the rest of the elements, in order to sort them.The vertical lines are used to delimit and show you the part of the array in which the iteration works.Elements to the left of A[j] that are greater than A[j] move one position to the right, and A[j] moves into the freed position.
Least but not last, we have the final sorted array.

Best, worst, and average cases

The best case performance has an O(n) complexity, or linear complexity.This occurs when the input array is already sorted.
The average case performance and the worst case performance, both have an O(n^2) complexity.
In the worst case performance, the input array is sorted in reverse order.

Related posts:

1. Determining an Algorithm’s Complexity
2. Introduction to Search Algorithms
3. Recursive Functions