Insertion Sort

Summary: In this tutorial, we will learn what Insertion sort algorithm is and how to implement the Insertion sort algorithm to sort an array in C and Java.

Introduction to Insertion sort Algorithm

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.

Wikipedia

Insertion sort is a stable sorting algorithm that is used to sort linear data structures such as array and list.

The algorithm sorts array elements one by one. On each iteration, the sorted partition of the array grows and the unsorted partition shrinks.

The black blocks represent the sorted partition and otherwise represent the unsorted partition of the array.

In the above example, the Insertion sort algorithm picks one element (red block) at a time and place it to its correct position in the sorted partition.

The algorithm repeats this process for every element and in the end, the array is sorted.

Insertion Sort Algorithm

Steps to implement Insertion Sort Algorithm:

1. Loop from i=1 to i<array.length
2. Select array[i] and assign pos=i.
3. Nest another Loop from j=i-1 to j>=0
4. Check if(array[i] < array [j]).
5. If yes then shift array[j] to the right (i.e. array[j+1]=array[j]) and assign pos=j.
6. If not then assign pos=j+1 break the nested loop.
7. End nested j loop.
8. Assign array[i] to index position pos (i.e. array[pos]=array[i]).
9. End i loop.

Here step-2 is selecting the array element and step-3 to step-7 shift all the elements to the right which are greater than the selected element.

Finally, step-8 places the selected element to its correct position.

Here is the implementation of the insertion sort algorithm in C and Java.

#include <stdio.h>
#include <stdlib.h>
void insertSort(int[], int);
void display(int[], int);
 
int main()
{
    int a[] = {8, 36, -51, 9, 21, 46, 2};
 
    printf("Unsorted array \n");
    display(a,7);
 
    insertSort(a, 7);
 
    printf("Sorted array \n");
    display(a,7);
 
    return 0;
}
 
void display(int a[], int size){
    for(int i=0; i< size; i++){
        printf("%d ", a[i]);
    }
    printf("\n");
}
 
void insertSort(int a[], int size){
    int temp, i, j, pos;
    for(i=1; i<size; i++){
        //Pick element
 
       temp = a[i];
        pos = i;
 
       
        //Place temp in the sorted partition
        for(j=i-1; j>=0; j--){
            if(temp < a[j]){
                a[j+1] = a[j];
                pos = j;
            } else {
                pos = j+1;
                break;
            }
        }
        a[pos] = temp;
    }
}

public class InsertionSort {
    int a[];
 
    public InsertionSort(int[] a) {
        this.a = a;
    }
 
    public void sort(int a[]){
        int temp, i, j, pos;
        for(i=1; i<a.length; i++){
            //Pick element
            temp = a[i];
            pos = i;
 
           //Place temp in the sorted partition
            for(j=i-1; j>=0; j--){
                if(temp < a[j]){
                    a[j+1] = a[j];
                    pos = j;
                } else {
                    pos = j+1;
                    break;
                }
            }
            a[pos] = temp;
        }
    }
}

public class App {
    public static void main(String args[]){
        int a[] = {8, 36, -51, 9, 21, 46, 2};
        InsertionSort is = new InsertionSort(a);
 
        System.out.println("Unsorted array ");
        display(a);
 
        is.sort(a);
 
        System.out.println("Sorted array ");
        display(a);
    }
 
    private static void display(int[] a) {
        for(int i=0; i< a.length; i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
}

Output

In the above program, the temp variable stores the copy of the selected element because on right swapping the greater elements its value gets overwritten in the array.

The pos variable, stores the correct position of the selected array element.

Insertion Sort Overview

• In-place algorithm – No extra array is needed.
• O(n²) time complexity – quadratic.
• Stable algorithm – Doesn’t interchange the same values in the array.
• Quite Efficient for data sets that are already substantially sorted.

In this tutorial, we learned what Insertion sort algorithm is and how to implement Insertion sort algorithm to sort an array in C and Java programming languages.