There are several basic algorithms for solving the array sorting problem . One of the most famous among them is sorting by inserts. Due to its clarity and simplicity, but low efficiency, this method is mainly used in teaching programming. It allows you to understand the basic sorting mechanisms.
Algorithm description
The essence of the insertion sorting algorithm is that a segment, ordered in the right way, is formed inside the source array. Each element is compared one by one with the tested part and inserted into place. Thus, after enumerating all the elements, they line up in the correct order.
The order of choice of elements can be any, they can be selected arbitrarily or according to some algorithm. Most often, sequential enumeration from the beginning of the array is used, where an ordered segment is formed.
The start of the sort might look like this:
- Take the first element of the array.
- Since there is nothing to compare it with, take the element itself for an ordered sequence.
- Go to the second item.
- Compare it with the first, based on the sorting rule.
- If necessary, swap elements.
- Take the first two elements for an ordered sequence.
- Go to the third item.
- Compare it with the second, if necessary, swap.
- If replacement is made, compare it with the first.
- Take three elements for an ordered sequence.
And so on until the end of the original array.
Sort inserts in real life
For clarity, it is worth giving an example of how this sorting mechanism is used in everyday life.
Take, for example, a wallet. In the banknote compartment, hundreds, five hundred and one thousandths of banknotes are in a mess. This is a mess, in such a mess it is difficult to immediately find the right piece of paper. An array of notes must be sorted.
The very first is a banknote of 1000 rubles, and immediately after it - 100. We take a hundred and place it in front. The third in a row - 500 rubles, the rightful place for her is between a hundred and a thousand.
In the same way, we sort the received cards when playing the "Fool", so that it is easier to navigate them.
Operators and helper functions
The insertion sorting method takes as input a source array to be ordered, a comparison function and, if necessary, a function that defines the rule for enumerating elements. Most often, the usual loop operator is used instead.
The first element in itself is an ordered set, so the comparison begins with the second.
An algorithm often uses an auxiliary function to exchange two values (swap). It uses an additional temporary variable, which requires memory and slightly slows down the code.
An alternative is the mass displacement of a group of elements and the subsequent insertion of the current into the vacated space. In this case, the transition to the next element occurs when the comparison gives a positive result, which indicates the correct order.
Implementation examples
The specific implementation largely depends on the programming language used, its syntax and structures.
A classic C language implementation using a temporary variable to exchange values:
int i, j, temp; for (i = 1; i < size; i++) { temp = array[i]; for (j = i - 1; j >= 0; j--) { if (array[j] < temp) break; array[j + 1] = array[j]; array[j] = temp; } }
PHP implementation:
function insertion_sort(&$a) { for ($i = 1; $i < count($a); $i++) { $x = $a[$i]; for ($j = $i - 1; $j >= 0 && $a[$j] > $x; $j--) { $a[$j + 1] = $a[$j]; } $a[$j + 1] = $x; } }
Here, first, all elements that do not meet the sorting condition are shifted to the right, and then the current element is inserted into the vacated space.
Java code using a while loop:
public static void insertionSort(int[] arr) { for(int i = 1; i < arr.length; i++){ int currElem = arr[i]; int prevKey = i - 1; while(prevKey >= 0 && arr[prevKey] > currElem){ arr[prevKey+1] = arr[prevKey]; arr[prevKey] = currElem; prevKey--; } } }
The general meaning of the code remains unchanged: each element of the array is sequentially compared with the previous ones and changed places with them if necessary.
Estimated work time
Obviously, in the best case, the input to the algorithm will be an array that is already ordered in the correct way. In this situation, the algorithm will simply have to check each element to make sure that it stands in its place without exchanges. Thus, the runtime will directly depend on the length of the original array O (n).
The worst case of input is an array sorted in reverse order. It will require a large number of permutations, the runtime function will depend on the number of elements squared.
The exact number of permutations for an absolutely disordered array can be calculated using the formula:
n*(n-1)/2
where n is the length of the original array. Thus, 4950 permutations are required to arrange 100 elements in the correct order.
The insertion method is very effective for sorting small or partially ordered arrays. However, it is not recommended to be used everywhere because of the high complexity of calculations.
The algorithm is used as a helper in many other more complex sorting methods.
Sort the same values
The insertion algorithm refers to the so-called stable sortings. This means that it does not interchange the same elements, but preserves their original order. The stability index in many cases is important for proper ordering.
The above is a great visual example of sorting inserts in a dance.