Q. Write a program to sort an array element in ascending order using Insertion Sort Algorithm.



Insertion Sort :- Insertion sort is a simple sorting algorithm that works out how to sort cards playing in our hands.

Ascending Order :- Numbers are said to be in ascending order when they are arranged from smallest to largest number. Such as 5, 9, 13, 17 and 21 are arranged in ascending order.

Insertion Sort Algorithm

START
     Step 1 : If it is the first element, it is already sorted. return 1;
     Step 2 : Pick next element
     Step 3 : Compare with all elements in the sorted sub-list
     Step 4 : Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
     Step 5 : Insert the value
     Step 6 : Repeat until list is sorted
STOP


Insertion Sort Program

  • C
  • C++
  • Java
  • Python
  • C#
  • PHP
  • // Insertion sort in C
    
    #include <stdio.h>
    void print_array(int arr[], int size)
    {
      for (int i = 0; i < size; i++)
      {
        printf("%d ", arr[i]);
      }
      printf("\n");
    }
    void insertion_sort(int arr[], int size)
    {
      for (int step = 1; step < size; step++)
      {
        int key = arr[step];
        int j = step - 1;
        while (key < arr[j] && j >= 0)
        {
          // For descending order, change key< arr[j] to key>arr[j].
          arr[j + 1] = arr[j];
          --j;
        }
        arr[j + 1] = key;
      }
    }
    int main()
    {
      int arr[] = {15, 50, -27, -4, 10};
      int size = sizeof(arr) / sizeof(arr[0]);
      insertion_sort(arr, size);
      printf("Sorted array in ascending order:\n");
      print_array(arr, size);
    }
    
    // Insertion sort in C++
    
    #include <iostream>
    using namespace std;
    
    void print_array(int arr[], int size)
    {
      for (int i = 0; i < size; i++)
      {
        cout << arr[i] << " ";
      }
      cout << endl;
    }
    void insertion_sort(int arr[], int size)
    {
      for (int step = 1; step < size; step++)
      {
        int key = arr[step];
        int j = step - 1;
        while (key < arr[j] && j >= 0)
        {
          // For descending order, change key< arr[j] to key>arr[j].
          arr[j + 1] = arr[j];
          --j;
        }
        arr[j + 1] = key;
      }
    }
    int main()
    {
      int arr[] = {15, 50, -27, -4, 10};
      int size = sizeof(arr) / sizeof(arr[0]);
      insertion_sort(arr, size);
      cout << "Sorted array in ascending order:\n";
      print_array(arr, size);
    }
    
    // Insertion sort in Java
    
    import java.util.Arrays;
    
    class LFC {
      void insertion_sort(int arr[]) {
        int size = arr.length;
        for (int step = 1; step < size; step++) {
          int key = arr[step];
          int j = step - 1;
          while (j >= 0 && key < arr[j]) {
            // For descending order, change key< arr[j] to key>arr[j].
            arr[j + 1] = arr[j];
            --j;
          }
          arr[j + 1] = key;
        }
      }
    
      public static void main(String args[]) {
        int[] arr = { 15, 50, -27, -4, 10 };
        LFC is = new LFC();
        is.insertion_sort(arr);
        System.out.println("Sorted Array in Ascending Order: ");
        System.out.println(Arrays.toString(arr));
      }
    }
    
    # Insertion sort in Python
    
    def insertion_sort(arr):
    
        for step in range(1, len(arr)):
            key = arr[step]
            j = step - 1
            while j >= 0 and key < arr[j]:
    
                # For descending order, change key< arr[j] to key >arr[j].
    
                arr[j + 1] = arr[j]
                j = j - 1
            arr[j + 1] = key
    
    
    arr = [15, 50, -27, -4, 10 ]
    insertion_sort(arr)
    print('Sorted Array in Ascending Order:')
    print(arr)
    
    using System;
    namespace InsertionSortDemo {
       class LFC {
          static void Main(string[] args) {
             int[] arr = new int[5] { 15, 50, -27, -4, 10  };
             int n = 5, i, j, val, flag;
            
             for (i = 1; i < n; i++) {
                val = arr[i];
                flag = 0;
                for (j = i - 1; j >= 0 && flag != 1; ) {
                   if (val < arr[j]) {
                      arr[j + 1] = arr[j];
                      j--;
                      arr[j + 1] = val;
                   }
                   else flag = 1;
                }
             }
             Console.Write("Sorted Array in Ascending Order: \n");   
             for (i = 0; i < n; i++) {
                Console.Write(arr[i] + " ");
             }     
          }
       }   
    }
    
         $arr = array(15, 50, -27, -4, 10);
     
        function insertion_sort($arr)
        {
            
            for ($i = 0; $i < count($arr); $i++) {
                   $val = $arr[$i];
               $j = $i-1;
        while($j>=0 && $arr[$j] > $val){
          $arr[$j+1] = $arr[$j];
          $j--;
        }
        $arr[$j+1] = $val;
            }
     
            return $arr;
        }
     
        $sorted_arr = insertion_sort($arr);
     echo "Sorted Array in Ascending Order: \n"; 
        for($i = 0; $i < 5; $i++) 
        echo $sorted_arr[$i]." ";
    
    // Insertion sort in C
    
    #include <stdio.h>
    void print_array(int arr[], int size)
    {
      for (int i = 0; i < size; i++)
      {
        printf("%d ", arr[i]);
      }
      printf("\n");
    }
    void insertion_sort(int arr[], int size)
    {
      for (int step = 1; step < size; step++)
      {
        int key = arr[step];
        int j = step - 1;
        while (key < arr[j] && j >= 0)
        {
          // For descending order, change key< arr[j] to key>arr[j].
          arr[j + 1] = arr[j];
          --j;
        }
        arr[j + 1] = key;
      }
    }
    int main()
    {
      int arr[] = {15, 50, -27, -4, 10};
      int size = sizeof(arr) / sizeof(arr[0]);
      insertion_sort(arr, size);
      printf("Sorted array in ascending order:\n");
      print_array(arr, size);
    }
    

    Output

    Sorted array in ascending order:
    -27 -4 10 15 50
    

    Recommended Programs

       Insertion Sort In Descending Order
       Finding Largest Element In An Array