public int[] insertionSort(int[] arr)
for (j = 1; j < arr.length; j++) {
int key = arr[j]
int i = j - 1
while (i > 0 and arr[i] > key) {
arr[i+1] = arr[i]
i -= 1
}
arr[i+1] = key
}
return arr;# 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)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;
}
}
5 4 7 9INSERTION-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