Insertion Sort gif uses animation to explain insertion sort, which repeatedly removes an element from the input data and inserts it into the position so that its value is between the previous and the next element. It works the way we sort when playing cards.
Table of Content
What is insertion sort?
Insertion sort works the same way as we play cards. When we grab a new card from a deck, we insert it into the right place so that all cards in our hand are ordered. The time complexity is O(n 2) time.
Insertion sort gif
Insertion sort code
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | import java.util.Arrays; public class InsertionSort { //Time O(n^2), Space O(1), n is array length public static void insertionSort(int[] arr) { int n = arr.length; for (int i = 1; i < n; i++) { int tmp = arr[i]; int j = i; while (j > 0 && arr[j-1] >= tmp ) { arr[j] = arr[j-1]; j--; } arr[j] = tmp; } } public static void main(String[] args) { int[] a = {19, 33, 4, 61, 5, 38, 36, 21, 0}; insertionSort(a); System.out.print("Insertion sort: "); System.out.println(Arrays.toString(a)); } } |
Javascript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | //Time O(n^2), Space O(1), n is array length function insertionSort(arr) { var n = arr.length; for (let i = 1; i < n; i++) { let tmp = arr[i]; let j = i; while (j > 0 && arr[j-1] >= tmp) { arr[j] = arr[j-1]; j--; } arr[j] = tmp; } } array = [19, 33, 4, 61, 5, 38, 36, 21, 0]; insertionSort(array); console.log("Insertion sort: "); console.log(array); |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #Time O(n^2), Space O(1), n is array length def insertionSort(arr) : n = len(arr) for i in range( 1, n) : tmp = arr[i] j = i while j > 0 and arr[j-1] >= tmp : arr[j] = arr[j-1] j -= 1 arr[j] = tmp array = [19, 33, 4, 61, 5, 38, 36, 21, 0] insertionSort(array) print("Insertion sort: ") print(array) |
Free download
Download Java, JavaScript and Python code
Algorithm types and algorithm examples