PYTHON

program for insertion sort

# another method similar to insertion sort

def insertionSort(arr):
    for i in range(1, len(arr)):
        k = i
        for j in range(i-1, -1, -1):
            if arr[k] < arr[j]:  # if the key element is smaller than elements before it
                temp = arr[k]  # swapping the two numbers
                arr[k] = arr[j]
                arr[j] = temp

                k = j  # assigning the current index of key value to k
        

arr = [5, 2, 9, 1, 10, 19, 12, 11, 18, 13, 23, 20, 27, 28, 24, -2]

print("original array 
", arr)
insertionSort(arr)
print("
Sorted array 
", arr)

Insertion sort algorithm

INSERTION-SORT(A)
   for i = 1 to n
   	key ← A [i]
    	j ← i – 1
  	 while j > = 0 and A[j] > key
   		A[j+1] ← A[j]
   		j ← j – 1
   	End while 
   	A[j+1] ← key
  End for 

insertion sorting

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class InsertionSorting {
    public static Scanner scanner = new Scanner(System.in);
    public static void main(String[] argh){
    int[] arrNotSorted = newArrInitilizer();
    enterValues(arrNotSorted);
    sortArray(arrNotSorted);
    print(arrNotSorted);

    }
  	//Print Array
    public static void print(int[] arr){
            System.out.print(Arrays.toString(arr));
    }
  
	/* looping from "i"(the incremented index in) ==> function
    public static int[] sortArray(int [] unsortedArr)
   	first we initilize an integer "value"= Array[from])
    this will be assigned later to the Array in the minmum value index 
    
    and while (from > 0) && (Array[from-1] > value) 
    we assign every next value to the previous one 
    
     eventually we decrement ("from")
   */
    public static void insertionSorting(int [] toBesorted, int from){
        int value = toBesorted[from];
        while(from > 0 && toBesorted[from-1] > value){
            toBesorted[from] = toBesorted[from-1];
         --from;
        }

        toBesorted[from] = value;

    }
 	
	/* Looping from index = 1, array with size one concidered sorted) 
    later "From" will be assigned to i in the function above */
    public static int[] sortArray(int [] unsortedArr){
        for(int i = 1 ; i < unsortedArr.length ; ++i){
            insertionSorting(unsortedArr,i);
        }

        return unsortedArr;
    }

  
  
    public static int[] newArrInitilizer() {
        System.out.println("Enter Array Size .");
        int arrSize = scanner.nextInt();
        int[] arr = new int[arrSize];
        return arr;
    }
		
  
  
    public static int [] enterValues(int[] arr){
        System.out.println("Array being initlized randomly with "+arr.length+" values.");
        for(int i = 0 ; i< arr.length ; ++i){
            arr[i] = (int) (Math.random()*10);
        }
        return  arr;
    }
}

InsertionSort

# Insertion sort in Python


def insertionSort(array):

    for step in range(1, len(array)):
        key = array[step]
        j = step - 1
        
        # Compare key with each element on the left of it until an element smaller than it is found
        # For descending order, change key<array[j] to key>array[j].        
        while j >= 0 and key < array[j]:
            array[j + 1] = array[j]
            j = j - 1
        
        # Place key at after the element just smaller than it.
        array[j + 1] = key


data = [9, 5, 1, 4, 3]
insertionSort(data)
print('Sorted Array in Ascending Order:')
print(data)