Insertion Sort

Write a program to sort the array. Use of insertion sort.

Example:

Input: arr[]= {3,2,5,4,1}
Output: 1 2 3 4 5

Approach

Java

import java.util.Arrays;

public class InsertionSort {
    public static void main(String args[]) throws Exception {

        int[] arr = { 3, 2, 5, 4, 1 };
        insertionSort(arr.length, arr);
    }

    static void insertionSort(int n, int[] arr) {
        for (int i = 0; i < n; i++) {
            int tmp = arr[i];
            int j = i;
            while (j > 0 && arr[j - 1] > tmp) {
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = tmp;

        }
        Arrays.stream(arr).forEach(e -> System.out.print(e + " "));
    }
}
// Time Complexity: O(n^2)
// Space Complexity: O(1)

C++

#include <bits/stdc++.h>
using namespace std;
//Function to sort the given
//array
void insertionSort(int arr[],int n)
{
    for(int i=0;i<n;i++)
      {
          int temp=arr[i];
          int j=i;
          while(j>0&&arr[j-1]>temp)
            {
               arr[j]=arr[j-1];
               j=j-1;
            }
          arr[j]=temp;
      }
}
int main()
{
    int arr[]={3,2,5,4,1};
    int n=sizeof(arr)/sizeof(arr[0]);
    insertionSort(arr,n);
    cout<<"Sorted Array is ";
    for(int i=0;i<n;i++)
       cout<<arr[i]<<" ";
    return 0;
}
//Time Complexity: O(n^2)
//Space Complexity:O(1)