Insertion Sort 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. O(n 2) average and worst. Insertion sort is the best of simple sorting. For random data this algorithm runs twice as fast as the bubble sort and faster than selection sort.
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) |
Doodle
Download Java, JavaScript and Python code
Insertion sort doodle
Selection sort