 # Insertion Sort Algorithm

##### Insertion Sort:

Insertion sort is a simple sorting algorithm that is relatively efficient for small lists and mostly sorted lists, and is often used as part of more sophisticated algorithms. It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list. In arrays, the new list and the remaining elements can share the array’s space, but insertion is expensive, requiring shifting all following elements over by one. Shell sort (see below) is a variant of insertion sort that is more efficient for larger lists.

##### Time Complexity of Insertion Sort :
Class Sorting algorithm Array О(n2) comparisons, swaps O(n) comparisons, O(1) swaps О(n2) comparisons, swaps О(n) total, O(1) auxiliary
##### Animated Example : ##### Psedo Code :
`public` `static` `void` `insertionSort(``int``[] array) {`
`for` `(``int` `i = ``0``; i < array.length - ``1``; i++) {`
`int` `j = i + ``1``;`
`int` `tmp = array[j];`
`while` `(j > ``0` `&& tmp > array[j-``1``]) {`
`array[j] = array[j-``1``];`
`j--;`
`}`
`array[j] = tmp;`
`}`
`}`
##### Complete Code :
``````public class InsertionSort {
public static void main(String args[]){

int a[]={1,3,5,6,12,22,12,7,8,9};
intInsertionSort(a);

}

public static void intInsertionSort(int[] a){
for (int i = 1; i <a.length ; i++) {
int temp = a[i];
int j;
for ( j = i-1; j >=0 && temp<a[j] ; j--) {

a[j+1] = a[j];

}
a[j+1] =temp;
printNumbers(a);

}
}

public static void printNumbers(int[] input){
for (int i = 0; i <input.length ; i++) {
System.out.print(input[i] + "," );

}
System.out.println("\n");
}
}``````

## Working with Augmented reality – ARCoreWorking with Augmented reality – ARCore

What is ARCore ARCore is Google’s platform for building augmented reality experiences. Using different APIs, ARCore enables your phone to sense its environment, understand the world and interact with information.