insertion sort

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//I Love Java
2import java.util.*;
3import java.io.*;
4import static java.util.stream.Collectors.toList;
5import java.util.stream.*;
6
7public class Insertion_Sort_P {
8    public static void main(String[] args) throws IOException {
9        BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
10
11        List<Integer> arr = Stream.of(buffer.readLine().replaceAll("\\s+$", " ").split(" ")).map(Integer::parseInt)
12                .collect(toList());
13
14        insertion_sort(arr);
15
16        System.out.println(arr);
17    }
18
19    public static void insertion_sort(List<Integer> arr) {
20        for (int i = 1; i <= arr.size() - 1; i++) {
21            steps(arr, i);
22        }
23    }
24
25    public static void steps(List<Integer> arr, int comp) {
26        for (int i = 0; i <= comp - 1; i++) {
27            if (arr.get(comp) < arr.get(i)) {
28                swap(arr, i, comp);
29            }
30        }
31    }
32
33    static void swap(List<Integer> arr, int i, int j) {
34        int temp = arr.get(i);
35        arr.set(i, arr.get(j));
36        arr.set(j, temp);
37    }
38}
39

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//insertion sort
2#include <iostream>
3
4using namespace std;
5void insertion_sort(int arr[],int n)
6{
7    int value,index;
8    for(int i=1;i<n;i++)
9    {
10        value=arr[i];
11        index=i;
12        while(index>0&&arr[index-1]>value)
13        {
14            arr[index]=arr[index-1];
15            index--;
16
17        }
18        arr[index]=value;
19    }
20}
21void display(int arr[],int n)
22{
23    for(int i=0;i<n;i++)
24    {
25        cout<<arr[i]<<" ";
26    }
27    cout<<endl;
28}
29
30int main()
31{
32    int n;
33    cout<<"enter the size of the array:"<<endl;
34    cin>>n;
35    int array_of_numbers[n];
36    cout<<"enter the elements of the array:"<<endl;
37    for(int i=0;i<n;i++)
38    {
39        cin>>array_of_numbers[i];
40    }
41    cout<<"array before sorting:"<<endl;
42    display(array_of_numbers,n);
43    insertion_sort(array_of_numbers,n);
44    cout<<"array after sorting is:"<<endl;
45    display(array_of_numbers,n);
46
47    return 0;
48}
49

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

1 function insertionSortIterativo(array A)
2     for i ← 1 to length[A] 
3       do value ← A[i]
4            j ← i-1
5        while j >= 0 and A[j] > value 
6          do A[j + 1] ← A[j]
7             j ← j-1
8        A[j+1] ← value;
9

1class Sort  
2{ 
3    static void insertionSort(int arr[], int n) 
4    { 
5        if (n <= 1)                             //passes are done
6        {
7            return; 
8        }
9
10        insertionSort( arr, n-1 );        //one element sorted, sort the remaining array
11       
12        int last = arr[n-1];                        //last element of the array
13        int j = n-2;                                //correct index of last element of the array
14       
15        while (j >= 0 && arr[j] > last)                 //find the correct index of the last element
16        { 
17            arr[j+1] = arr[j];                          //shift section of sorted elements upwards by one element if correct index isn't found
18            j--; 
19        } 
20        arr[j+1] = last;                            //set the last element at its correct index
21    } 
22
23    void display(int arr[])                 //display the array
24    {  
25        for (int i=0; i<arr.length; ++i) 
26        {
27            System.out.print(arr[i]+" ");
28        } 
29    } 
30 
31       
32    public static void main(String[] args) 
33    { 
34        int arr[] = {22, 21, 11, 15, 16}; 
35       
36        insertionSort(arr, arr.length); 
37        Sort ob = new Sort();
38        ob.display(arr); 
39    } 
40} 
41

1 function insertionSortRicorsivo(array A, int n)
2     if n>1
3        insertionSortRicorsivo(A,n-1)
4        value ← A[n-1]
5        j ← n-2
6        while j >= 0 and A[j] > value 
7         do A[j + 1] ← A[j]
8            j ← j-1
9        A[j+1] ← value
10