insertion sort java

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])