Input: A sequence of ‘n’ numbers. [a(1),a(2),...a(n)]
Output: A permutation (reordering) of the input sequence such that [a(1)<=a(2)<=...a(n)]
Insertion is a good algorithm for sorting a small number of elements.
let insertionSort = function(arr, n){let i, key, j;for (i = 1; i < n; i++){// Current elementkey = arr[i];// Predecessorj = i - 1;// Move elements one position ahead of their current index that is greater than keywhile(j >= 0 && arr[j] > key){arr[j + 1] = arr[j];j = j - 1}// Move key into the proper evaluated positionarr[j + 1] = key;}return arr;}let arr = [21,17,3,11,6];let n = arr.length;insertionSort(arr, n);// Result: [ 3, 6, 11, 17, 21 ]
The inner ‘while’ loop works by moving preceding elements one position forward, opening the correct position for ‘key.’ Due to our loop condition, the loop can execute more than once when our’ while’ loop exits.
The outer for loop ends when i = n,
the array’s length.
def insertionSort(arr):# Traverse 1 through len(arr)for i in range(1, len(arr)):#Ccurrent elementkey = arr[i]# Predecessorj = i - 1# Move elements one position ahead of their current index that is greater than keywhile j >= 0 and arr[j] > key :arr[j + 1] = arr[j]j -= 1# Move key into the proper evaluated positionarr[j + 1] = keyreturn arrarr = [21,17,3,11,6]insertionSort(arr)# Result: [ 3, 6, 11, 17, 21 ]
Insertion sort is an incremental algorithm with an O(n^2) time complexity. Instructions are executed one after the other with no concurrent operations.
Best case: The input array elements are already sorted. Worst case: Maximum time to sort when our input array is sorted in reverse order.
Legal Stuff