This is the third day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Insertion sort

When we play poker, we always draw the top card in the deck and arrange it in order in our hand.

Insertion sort means that in the elements to be sorted, assuming that the first n-1 number (where n>=2) is already sorted, insert the NTH number into the previous sorted order, and then find the appropriate position, so that the insertion of the NTH number in the sequence is also sorted.

  1. For unsorted data (usually take two elements of an array and treat the first element as an ordered array), scan the sorted sequence from left to right to find the appropriate position and insert it.
  2. In order to make room for the elements to be inserted, we need to move the sorted elements after the insertion position back one bit.

Code implementation

Implement sort for the following arrays: {15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1}

Dynamic graph demonstration

Code implementation

public class InsertionSort { public static final int[] ARRAY = {15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1}; public static int[] sort(int[] array) { if (array.length == 0) { return array; } // The data to be sorted has been sorted int current; for (int i = 0; i < array.length - 1; I ++) {// Index of sorted data int index = I; current = array[index + 1]; While (index >= 0 && current < array[index]) {array[index + 1] = array[index]; index--; } // Insert array[index + 1] = current; } return array; } public static void print(int[] array) { for (int i : array) { System.out.print(i + " "); } System.out.println(""); } public static void main(String[] args) { print(ARRAY); System.out.println("============================================"); print(sort(ARRAY)); }}Copy the code

Time complexity

In the figure above, the first cycle is compared once, the second cycle is compared twice, and so on, so that the last cycle is compared n-1 times:

1 + 2 + 3 +... + n-1 = n*(n-1)/2Copy the code

In other words, in the worst case (reverse order), the time complexity of the comparison is O(n2).

In the optimal case, where the while loop is always false, all you need to do is compare the current number to the previous number, and then you need n minus one comparison, and the time is O(n).

Algorithm stability

When you compare, if two numbers are equal, you don’t move them, you don’t change the order of the two numbers, so insertion sort is stable.