How Insertion Sort Works?
Insertion sort loops over an array. At each iteration, we will insert the element at current index into the sub-array before it. The element should be inserted at the position where the element before is less or equal to it, and the element after is greater or equal to it. So after insertion, all elements before the current index will be sorted. After we go over the entire array, all elements are sorted.
Animated GIF of the Insertion Sort
Insertion Sort Runtime and Space Complexity
Worst-case performance: О(n2) (array sorted in reverse order)
Best-case performance: O(n) (array sorted in desired order)
Average performance: О(n2)
Space Complexity: О(n) total, O(1) auxiliary
Insertion Sort in 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 |
import java.util.Arrays; public class MyClass { public static void main(String args[]) { // data int[] arr = {5, 3, 8, 11, 4, 12, 7, 9, 8, 10}; // insertion sorting for(int i = 1; i < arr.length; i++){ for(int j = i; j > 0; j--){ if(arr[j] < arr[j-1]){ int temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; }else{ break; } } } //output result System.out.println(Arrays.toString(arr)); } } |
Insertion Sort in Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
# insertion sort def insertionSort(list): for i in range(1, len(list)): for j in reversed(range(1, i)): if (list[j] < list[j - 1]): temp = list[j] list[j] = list[j - 1] list[j - 1] = temp else: break # print result print(list) # data list = [5, 3, 8, 11, 4, 12, 7, 9, 8, 10] insertionSort(list) |
Insertion Sort in PHP
|
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 |
<?php // insertion sort function insertionSort($arr) { for($i = 0; $i < count($arr); $i++){ for($j = $i; $j > 0; $j--){ if($arr[$j] < $arr[$j - 1]){ $temp = $arr[$j]; $arr[$j] = $arr[$j - 1]; $arr[$j - 1] = $temp; }else{ break; } } } //print result print_r($arr); } // data $arr = array(5, 3, 8, 11, 4, 12, 7, 9, 8, 10); insertionSort($arr); ?> |
Insertion Sort in Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
var array = [5, 3, 8, 11, 4, 12, 7, 9, 8, 10]; insertionSort(array); function insertionSort(array) { for(var i = 0; i < array.length; i++) { for(var j = i; j > 0; j--) { if (array[j] < array[j-1]){ var temp = array[j]; array[j] = array[j-1]; array[j-1] = temp; }else{ break; } } } console.log(array); } |