Direct insert sort
The idea of inserting the sorting directly is easy to understand, it looks like this:
1. Divide the array to be sorted into two parts: sorted and unsorted. At the beginning, the first element is considered to be sorted.
2. Start with the second element, find the appropriate position of the element in the sorted subarray and insert it.
3. Repeat the above process until the last element is inserted into the ordered subarray.
4. Sorting is completed.
Example:
The idea is simple, but the code is not as easy to write as bubble sorting. First of all, how to determine the right position? Greater than or equal to the left, less than or equal to the right? No, many boundary conditions need to be considered, and there are too many judgments. Secondly, inserting elements into an array will inevitably require moving a large number of elements. How to control their movement?
In fact, this is not a problem with the algorithm itself, and it has something to do with the programming language. Sometimes the algorithm itself is already very mature, and it still needs to be slightly changed when it comes to the specific programming language. What we are talking about here is Java algorithm, so let’s talk about Java.
To solve the above problem, we have made a little refinement of the second step. We do not start comparison from the starting position of the sub-array, but start inverse comparison from the tail of the sub-array. As long as it is larger than the number that needs to be inserted, we move backwards. Until the number is not greater than the number, then the number to be inserted will be placed in this empty position. Therefore, we can write the following code:
InsertArray.java
public class InsertArray { // Array private long[] arr; // The size of valid data in the array private int elems; // Default constructor public InsertArray() { arr = new long[50]; } public InsertArray(int max) { arr = new long[max]; } // Insert data public void insert(long value) { arr[elems] = value; elems++; } // Show data public void display() { for (int i = 0; i < elems; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // Insert sort public void insertSort() { long select = 0L; for(int i = 1; i < elems; i++) { select = arr[i]; int j = 0; for(j = i;j > 0 && arr[j - 1] >= select; j--) { arr[j] = arr[j - 1]; } arr[j] = select; } }} Test class:
TestInsertArray.java
public class TestInsertArray { public static void main(String[] args) { InsertArray iArr = new InsertArray(); iArr.insert(85); iArr.insert(7856); iArr.insert(12); iArr.insert(8); iArr.insert(5); iArr.insert(56); iArr.display(); iArr.insertSort(); iArr.display(); }} Print result:
Algorithm performance/complexity
Now let’s discuss the time complexity of the direct insertion algorithm. Regardless of the input, the algorithm always performs n-1 rounds of sorting. However, since the insertion point of each element is uncertain and greatly affected by the input data, its complexity is not certain. We can discuss the best, worst and average situations.
1. Best case: From the characteristics of the algorithm, it can be seen that when the array to be arranged itself is in positive order (the array is ordered and the order is the same as the required order, which is in ascending order under our discussion premise). The reason is that in this case, each element only needs to be compared once and does not need to be moved. The time complexity of the algorithm is O(n);
2. Worst case: Obviously, when the array to be arranged is in reverse order, it is the worst case. In this case, our number of comparisons per round is i-1 and the number of assignments is i. The total number of times is the sum of the first n terms of the series 2n-1, that is, n^2. The time complexity of the algorithm is O(n^2);
3. Average situation: From the above analysis, we can obtain that the number of operations of the algorithm under the average situation is approximately (n^2)/2 (Note: The calculation here is based on assignment and comparison. If it is based on movement and comparison, it is approximately n^2/4). Obviously, the time complexity is still O(n^2).
As for the spatial complexity of the algorithm, all movements are performed inside the data. The only overhead is that we introduced a temporary variable (some data structures are called "sentinels" in books), so its spatial complexity (extra space) is O(1).
Algorithm stability
Since you only need to find a position that is not greater than the current number and do not need to swap, inserting the sort directly is a stable sorting method.
Algorithm variants
If there is a lot of data to be arranged, then it will cause a lot of overhead every time you look from behind to front. In order to improve the search speed, Binary Search can be used for performance optimization. Because the efficiency of binary search is very high, O(n) complexity is ensured, and the search efficiency can be greatly improved when there are more data or the input data tends to be at the worst. In some books, this method is called folding and half insert sorting. Its code implementation is quite complicated and can be posted if you have time in the future.
In addition, there are 2-way insert sorts and table insert sorts. 2-way insertion sort is further improved on the basis of folding and half insertion sort, and its number of movements is greatly reduced, about n^2/8. However, it does not avoid the number of movements and does not reduce the complexity level. The table insertion sort completely changes the storage structure and does not move records, but a linked list needs to be maintained, and the pointer of the linked list is modified instead of moving records. Therefore, its complexity is still O(n^2).
For 2-way insertion sort and table insertion sort, you can refer to the book "Data Structure" edited by Yan Weimin and Wu Weimin.
Algorithm applicable scenarios
Insertion sorting is not applicable when the array is large due to the complexity of O(n^2). However, when there is relatively little data, it is a good choice, generally used as an expansion for quick sorting. For example, in the sort algorithm of STL and the qsort algorithm of stdlib, insert sorting is used as a supplement to quick sorting and is used to sort a small number of elements. For example, in the implementation of the sort method used in JDK 7 java.util.Arrays, when the length of the array to be sorted is less than 47, insert sorting will be used.