You believe what a person says because they tell you what you want to hear. ———— Claire McFaul, FerryMan

This is the 10th day of my participation in Gwen Challenge

First, algorithm thought

Insertion sort is also a brute force sorting algorithm, which places unsorted elements in place in each iteration.

Insertion sort works in a similar way to how we sort cards in a card game. We assume that the first card is sorted, then we select an unsorted card, if the unsorted card is larger than the one in hand, place it on the right, otherwise on the left, and in the same way the other unsorted cards are removed and placed in the correct position.

1. The illustration

Suppose we try to sort the elements in ascending order.

Second, the work process

Suppose we need to sort the following array.

1. Assuming the first element in the array is sorted, take the second element and store it separately inkeyIn, the first element

If the first element is larger than the key, the key precedes the first element.

2. Now that the first two elements are sorted, take the third element and compare it to the element on the left, and place it after any element smaller than it, or at the beginning of the array if there is none.

3. Repeat the above steps to place each unsorted element in the correct position.

Three, code implementation

1. Pseudo-code implementation

insertionSort(array)
  mark first element as sorted
  for each unsorted element X
    'extract' the element X
    for j <- lastSortedIndex down to 0
      if current element j > X
        move sorted element to the right by 1
    break loop and insert X here
end insertionSort
Copy the code

2. Java implementation

import java.util.Arrays;

/** * insert sort **@className: InsertSort
 * @date: 2021/6/24 17:07 * /
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {9.5.1.4.3};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void insertSort(int[] arr) {
        int length = arr.length;
        // Start with the second element
        for (int i = 1; i < length; i++) {
            // Define a pointer to the first element
            int j = i - 1;
            // Define a key to hold the next element
            int key = arr[i];
            // Iterate over each element to the left of the key until you find one smaller than it
            while (j >= 0 && arr[j] > key) {
                // Move elements larger than key back one bit to leave space for the key
                arr[j + 1] = arr[j];
                j--;
            }
            // Place the key after the smaller element, arr[j], to complete the sorting round
            arr[j + 1] = key; }}}Copy the code

4. Sorting complexity

1. Time complexity

• Worst-case complexity O(n2) : Suppose an array is sorted in ascending order, and you want to sort it in descending order. In this case, worst-case complexity emerges. Each element must be compared to every other element, so for each NTH element, multiple comparisons are made. So the total number of comparisons is O(n2).
• Optimal case complexity O(n2) : When the array is already sorted, the outer loop runs n times, while the inner loop does not run at all and only compares n times, so the complexity is linear.
• Average case complexity O(n2) : This occurs when the elements of the array are in a disorderly order (neither up nor down).

The time complexity of selection sort is the same in all cases, and the smallest element must be found and placed in the right place at each step.

2. Space complexity

• The space complexity is O(1) because of the extra variables.

Insert sort application

Insert sort is used when:

• The array has a small number of elements
• There are only a few elements left to sort

Insertion sort is a simple sorting algorithm that builds a final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heap sort, or merge sort.

Reference article:

www.programiz.com/dsa/inserti…