AlphaCodingSkills

Insertion Sort


Advertisements

Previous Page Next Page

Insertion sort is based on the idea of consuming one element from unsorted array and inserting it at the correct position in the sorted array. This will result into increasing the length of the sorted array by one and decreasing the length of unsorted array by one after each iteration.

Example:

To understand the insertion sort, lets consider an unsorted array [23, 1, 10, 5, 2] and discuss each step taken to sort the array in ascending order. In every pass, one element is taken from the unsorted array and inserted it at the correct position in the sorted array.

First Pass: The whole array is unsorted array and 23 is taken to be inserted into the sorted array. As 23 is the first element of sorted array and has no elements to be compared with, it remains at its position.

Second Pass: 1 is the taken from unsorted array to insert into sorted array. It is compared with all elements of sorted array and found that 23 is the only number which is greater than 1. 1 is inserted into the sorted array and position of 23 is shifted by one place in the array. This resulted into increasing the length of sorted array by one and decreasing the length of unsorted array by one.

Third Pass: 10 is taken from the unsorted array and compared with all elements of sorted array. 23 is the only number in the sorted array which is greater than 10. 10 is inserted into the sorted array and position of 23 is shifted by one place in the array.

Fourth Pass: 5 is compared with all elements of sorted array and it is found that 10 and 23 are the numbers which need to be shifted by one place to insert 5 into the sorted array.

Fifth Pass: To insert 2 into the sorted array, 5, 10 and 23 are shifted by one place.

insertion Sort

Implementation of Insertion Sort



# function for insertion sort
def insertionsort(MyList):
  for i in range(len(MyList)): 
    curr = MyList[i] 
    j = i-1
    while j >= 0 and curr < MyList[j] : 
      MyList[j + 1] = MyList[j]
      MyList[j] = curr
      j = j - 1

# test insertion sort code                 
MyList = [1, 10, 23, 50, 4, 9, -4]
print("Original List")
for i in MyList:
  print(i, end=" ")
print("\n")

insertionsort(MyList)
print("Sorted List")
for i in MyList:
  print(i, end=" ")

Output

Original List
1 10 23 50 4 9 -4 

Sorted List
-4 1 4 9 10 23 50 



public class MyClass {
  // function for insertion sort
  static void insertionsort(int Array[]) {
    int n = Array.length;
    for(int i=0; i<n; i++) 
    {
      int curr = Array[i];
      int j = i - 1;
      while(j >= 0 && curr < Array[j])
      {
        Array[j + 1] = Array[j];
        Array[j] = curr;
        j = j - 1;
      }
    }
  }

  // function to print array
  static void PrintArray(int Array[]) 
    { 
        int n = Array.length; 
        for (int i=0; i<n; i++) 
        {  
          System.out.print(Array[i] + " "); 
        }
        System.out.println(); 
    } 

  //test insertion sort code
  public static void main(String[] args) {
    int[] MyArray = {1, 10, 23, 50, 4, 9, -4};
    System.out.println("Original Array");
    PrintArray(MyArray);

    insertionsort(MyArray);
    System.out.println("\nSorted Array");
    PrintArray(MyArray);  
  }
}

Output

Original Array
1 10 23 50 4 9 -4 

Sorted Array
-4 1 4 9 10 23 50 



#include <iostream>
using namespace std;

  // function for insertion sort
  static void insertionsort(int Array[], int n) 
  {
    for(int i=0; i<n; i++) 
    {
       int curr = Array[i];
       int j = i - 1;
       while(j >= 0 && curr < Array[j])
        {
          Array[j + 1] = Array[j];
          Array[j] = curr;
          j = j - 1;
        }
    }
  }

  // function to print array
  static void PrintArray(int Array[], int n) 
  { 
    for (int i=0; i<n; i++) 
    {  
      cout<<Array[i]<<" "; 
    }
    cout<<"\n"; 
  } 

 // test insertion sort code
 int main (){
    int MyArray[] = {1, 10, 23, 50, 4, 9, -4};
    int n = sizeof(MyArray) / sizeof(MyArray[0]); 
    cout<<"Original Array\n";
    PrintArray(MyArray, n);

    insertionsort(MyArray, n);
    cout<<"\nSorted Array\n";
    PrintArray(MyArray, n);
    return 0;
 }

Output

Original Array
1 10 23 50 4 9 -4 

Sorted Array
-4 1 4 9 10 23 50



#include <stdio.h>

  // function for insertion sort
  static void insertionsort(int Array[], int n) 
  {
    for(int i=0; i<n; i++) 
    {
       int curr = Array[i];
       int j = i - 1;
       while(j >= 0 && curr < Array[j])
        {
          Array[j + 1] = Array[j];
          Array[j] = curr;
          j = j - 1;
        }
    }
  }

  // function to print array
  static void PrintArray(int Array[], int n) 
  { 
    for (int i=0; i<n; i++) 
    {  
      printf("%i ",Array[i]); 
    }
    printf("\n"); 
  } 

 // test insertion sort code
 int main (){
    int MyArray[] = {1, 10, 23, 50, 4, 9, -4};
    int n = sizeof(MyArray) / sizeof(MyArray[0]); 
    printf("Original Array\n");
    PrintArray(MyArray, n);

    insertionsort(MyArray, n);
    printf("\nSorted Array\n");
    PrintArray(MyArray, n);
    return 0;
 }

Output

Original Array
1 10 23 50 4 9 -4 

Sorted Array
-4 1 4 9 10 23 50 



using System;

namespace MyApplication { 
   class MyProgram {
       // function for insertion sort
       static void insertionsort(int[] Array) 
       {
        int n = Array.Length;
        for(int i=0; i<n; i++) 
        {
          int curr = Array[i];
          int j = i - 1;
          while(j >= 0 && curr < Array[j])
          {
            Array[j + 1] = Array[j];
            Array[j] = curr;
            j = j - 1;
          }
        }
       }

     // function to print array
     static void PrintArray(int[] Array) 
     { 
        int n = Array.Length; 
        for (int i=0; i<n; i++) 
        {  
          Console.Write(Array[i] + " "); 
        }
        Console.Write("\n"); 
     } 
 
    // test insertion sort code
    static void Main(string[] args) {
     int[] MyArray = {1, 10, 23, 50, 4, 9, -4};
     Console.Write("Original Array\n");
     PrintArray(MyArray);

     insertionsort(MyArray);
     Console.Write("\nSorted Array\n");
     PrintArray(MyArray);  
    }
  }
}

Output

Original Array
1 10 23 50 4 9 -4 

Sorted Array
-4 1 4 9 10 23 50

Time Complexity:

Insertion sort takes maximum time if the array is in the reverse order and minimum time when the array is already sorted. In worst case scenario every element is compared with all other elements. Therefore, for N elements there will be comparison hence the time complexity of insertion sort is O(N²).


Previous Page Next Page