Insertion Sort

Summary: In this tutorial, we will learn what the 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.

Insertion Sort Visualization

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
    1. Check if(array[i] < array [j]).
    2. If yes then shift array[j] to the right (i.e. array[j+1]=array[j] and assign pos=j)
    3. If not then assign pos=j+1 break the nested loop.
  4. End nested j loop.
  5. Assign array[i] to index position pos (i.e. array[pos]=array[i]).
  6. End i loop.

Here we select the array element in step-2 and shift all the elements greater than it to the right from step-3 to step-7.

Finally, in step-8, we place the selected element in its correct position.

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

Python

def insertionSort(arr):
    
    for i in range(1, len(arr)):
        element = arr[i]
        pos = i
        for j in range(i-1, -1, -1):
            if arr[j] > element:
                arr[j+1] = arr[j]
                pos = j
            else:
                break
        arr[pos] = element
        
    return arr

if __name__ == '__main__':
    arr = [8, 36, -51, 9, 21, 46, 2]
    print(arr)
    
    insertionSort(arr)
    print(arr)

C

#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;
    }
}

Java

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

Unsorted array
8 36 -51 9 21 46 2
Sorted array
-51 2 8 9 21 36 46

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.

Leave a Reply