1/**
2* Insertion sort algorithm, O(n^2) time complexity.
3*/
4public static void insertionSort(int[] arr) {
5 int n = arr.length;
6 for(int i = 1; i < n; i++) {
7 int key = arr[i];
8 int j = i - 1;
9 //shift until you find the position to place the element 'key'
10 while(j >= 0 && arr[j] > key) {
11 arr[j+1] = arr[j];
12 j--;
13 }
14 //place element 'key' in the correct position in the sorted part of the array
15 arr[j+1] = key;
16 }
17}
1Insertion program
2public class InsertionSortExample
3{
4 public void sort(int[] arrNum)
5 {
6 int number = arrNum.length;
7 for(int a = 1; a < number; ++a)
8 {
9 int keyValue = arrNum[a];
10 int b = a - 1;
11 while(b >= 0 && arrNum[b] > keyValue)
12 {
13 arrNum[b + 1] = arrNum[b];
14 b = b - 1;
15 }
16 arrNum[b + 1] = keyValue;
17 }
18 }
19 static void displayArray(int[] arrNum)
20 {
21 int num = arrNum.length;
22 for(int a = 0; a < num; ++a)
23 {
24 System.out.print(arrNum[a] + " ");
25 }
26 System.out.println();
27 }
28 public static void main(String[] args)
29 {
30 int[] arrInput = { 50, 80, 10, 30, 90, 60 };
31 InsertionSortExample obj = new InsertionSortExample();
32 obj.sort(arrInput);
33 displayArray(arrInput);
34 }
35}
1// Java program for implementation of Insertion Sort
2public class InsertionSort
3{
4 /*Function to sort array using insertion sort*/
5 void sort(int arr[])
6 {
7 int n = arr.length;
8 for (int i=1; i<n; ++i)
9 {
10 int key = arr[i];
11 int j = i-1;
12
13 /* Move elements of arr[0..i-1], that are
14 greater than key, to one position ahead
15 of their current position */
16 while (j>=0 && arr[j] > key)
17 {
18 arr[j+1] = arr[j];
19 j = j-1;
20 }
21 arr[j+1] = key;
22 }
23 }
24 /* A utility function to print array of size n*/
25 static void printArray(int arr[])
26 {
27 int n = arr.length;
28 for (int i=0; i<n; ++i)
29 System.out.print(arr[i] + " ");
30 System.out.println();
31 }
32 // Driver method
33 public static void main(String args[])
34 {
35 int arr[] = {12, 11, 13, 5, 6};
36 InsertionSort ob = new InsertionSort();
37 ob.sort(arr);
38 printArray(arr);
39 }
40}
1// Por ter uma complexidade alta,
2// não é recomendado para um conjunto de dados muito grande.
3// Complexidade: O(n²) / O(n**2) / O(n^2)
4// @see https://www.youtube.com/watch?v=TZRWRjq2CAg
5// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
6
7function insertionSort(vetor) {
8 let current;
9 for (let i = 1; i < vetor.length; i += 1) {
10 let j = i - 1;
11 current = vetor[i];
12 while (j >= 0 && current < vetor[j]) {
13 vetor[j + 1] = vetor[j];
14 j--;
15 }
16 vetor[j + 1] = current;
17 }
18 return vetor;
19}
20
21insertionSort([1, 2, 5, 8, 3, 4])