insertion sort python
def insertionSort(alist):
for i in range(1,len(alist)):
#element to be compared
current = alist[i]
#comparing the current element with the sorted portion and swapping
while i>0 and alist[i-1]>current:
alist[i] = alist[i-1]
i = i-1
alist[i] = current
#print(alist)
return alist
print(insertionSort([5,2,1,9,0,4,6]))
// C++ program for insertion sort
#include <bits/stdc++.h>
using namespace std;
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
/* Driver code */
int main()
{
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printArray(arr, n);
return 0;
}
// This is code is contributed by rathbhupendra
// Por ter uma complexidade alta,
// não é recomendado para um conjunto de dados muito grande.
// Complexidade: O(n²) / O(n**2) / O(n^2)
// @see https://www.youtube.com/watch?v=TZRWRjq2CAg
// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
function insertionSort(vetor) {
let current;
for (let i = 1; i < vetor.length; i += 1) {
let j = i - 1;
current = vetor[i];
while (j >= 0 && current < vetor[j]) {
vetor[j + 1] = vetor[j];
j--;
}
vetor[j + 1] = current;
}
return vetor;
}
insertionSort([1, 2, 5, 8, 3, 4])