1#insertion sort
2def insert(arr):
3 for i in range(1,len(arr)):
4 while arr[i-1] > arr[i] and i > 0:
5 arr[i], arr[i-1] = arr[i-1], arr[i]
6 i -= 1
7 return arr
8arr = [23, 55, 12, 99, 66, 33]
9print(insert(arr))
1# another method similar to insertion sort
2
3def insertionSort(arr):
4 for i in range(1, len(arr)):
5 k = i
6 for j in range(i-1, -1, -1):
7 if arr[k] < arr[j]: # if the key element is smaller than elements before it
8 temp = arr[k] # swapping the two numbers
9 arr[k] = arr[j]
10 arr[j] = temp
11
12 k = j # assigning the current index of key value to k
13
14
15arr = [5, 2, 9, 1, 10, 19, 12, 11, 18, 13, 23, 20, 27, 28, 24, -2]
16
17print("original array \n", arr)
18insertionSort(arr)
19print("\nSorted array \n", arr)
20
1def insertionSort(arr):
2 for i in range(1, len(arr)):
3 key = arr[i]
4 j = i-1
5 while j >= 0 and key < arr[j] :
6 arr[j + 1] = arr[j]
7 j -= 1
8 arr[j + 1] = key
1#include <bits/stdc++.h>
2
3using namespace std;
4
5void insertionSort(int arr[], int n)
6{
7 int i, temp, j;
8 for (i = 1; i < n; i++)
9 {
10 temp = arr[i];
11 j = i - 1;
12
13 while (j >= 0 && arr[j] > temp)
14 {
15 arr[j + 1] = arr[j];
16 j = j - 1;
17 }
18 arr[j + 1] = temp;
19 }
20}
21
22int main()
23{
24 int arr[] = { 1,4,2,5,333,3,5,7777,4,4,3,22,1,4,3,666,4,6,8,999,4,3,5,32 };
25 int n = sizeof(arr) / sizeof(arr[0]);
26
27 insertionSort(arr, n);
28
29 for(int i = 0; i < n; i++){
30 cout << arr[i] << " ";
31 }
32
33 return 0;
34}
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])
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.Scanner;
4
5public class InsertionSorting {
6 public static Scanner scanner = new Scanner(System.in);
7 public static void main(String[] argh){
8 int[] arrNotSorted = newArrInitilizer();
9 enterValues(arrNotSorted);
10 sortArray(arrNotSorted);
11 print(arrNotSorted);
12
13 }
14 //Print Array
15 public static void print(int[] arr){
16 System.out.print(Arrays.toString(arr));
17 }
18
19 /* looping from "i"(the incremented index in) ==> function
20 public static int[] sortArray(int [] unsortedArr)
21 first we initilize an integer "value"= Array[from])
22 this will be assigned later to the Array in the minmum value index
23
24 and while (from > 0) && (Array[from-1] > value)
25 we assign every next value to the previous one
26
27 eventually we decrement ("from")
28 */
29 public static void insertionSorting(int [] toBesorted, int from){
30 int value = toBesorted[from];
31 while(from > 0 && toBesorted[from-1] > value){
32 toBesorted[from] = toBesorted[from-1];
33 --from;
34 }
35
36 toBesorted[from] = value;
37
38 }
39
40 /* Looping from index = 1, array with size one concidered sorted)
41 later "From" will be assigned to i in the function above */
42 public static int[] sortArray(int [] unsortedArr){
43 for(int i = 1 ; i < unsortedArr.length ; ++i){
44 insertionSorting(unsortedArr,i);
45 }
46
47 return unsortedArr;
48 }
49
50
51
52 public static int[] newArrInitilizer() {
53 System.out.println("Enter Array Size .");
54 int arrSize = scanner.nextInt();
55 int[] arr = new int[arrSize];
56 return arr;
57 }
58
59
60
61 public static int [] enterValues(int[] arr){
62 System.out.println("Array being initlized randomly with "+arr.length+" values.");
63 for(int i = 0 ; i< arr.length ; ++i){
64 arr[i] = (int) (Math.random()*10);
65 }
66 return arr;
67 }
68}
69