There are several basic algorithms for solving the problem of sorting an array. One of the most famous among them is insertion sort. Due to its clarity and simplicity, but low efficiency, this method is used mainly in teaching programming. It allows you to understand the basic sorting mechanisms.
Description of the algorithm
The essence of the insertion sort algorithm is that a properly ordered segment is formed inside the initial array. Each element is compared one by one with the checked part and inserted into the right place. Thus, after iterating through all the elements, they line up in the correct order.
The order of selecting elements can be any, they can be selected arbitrarily or according to some algorithm. Most often, sequential enumeration is used from the beginning of the array, where an ordered segment is formed.
The start of sorting might look like this:
- Take the first element of the array.
- Since there is nothing to compare it with, take the element itself as orderedsequence.
- Go to the second item.
- Compare it with the first one based on the sort rule.
- If necessary, swap elements in places.
- Take the first two elements as an ordered sequence.
- Go to the third item.
- Compare it with the second one, swap if necessary.
- If the replacement is made, compare it with the first one.
- Take three elements as an ordered sequence.
And so on until the end of the original array.
Real life insertion sort
For clarity, it is worth giving an example of how this sorting mechanism is used in everyday life.
Take, for example, a wallet. Hundred, five-hundred, and thousand-dollar bills lie in disorder in the banknote compartment. This is a mess, in such a hodgepodge it is difficult to immediately find the right piece of paper. The array of banknotes 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 is 500 rubles, the rightful place for it is between a hundred and a thousand.
In the same way we sort the received cards when playing the "Fool" to make it easier to navigate them.
Operators and helper functions
The insertion sort method takes as input an initial array to be sorted, a comparison function, and, if necessary, a function that determines the rule for enumerating elements. Most often used insteadregular loop statement.
The first element is itself an ordered set, so the comparison starts from the second.
The algorithm often uses a helper function to exchange two values (swap). It uses an additional temporary variable, which consumes memory and slows down the code a bit.
An alternative is to mass shift a group of elements and then insert the current one into the free space. In this case, the transition to the next element occurs when the comparison gave a positive result, which indicates the correct order.
Implementation examples
The specific implementation largely depends on the programming language used, its syntax and structures.
Classic C implementation using a temporary variable to exchange values:
int i, j, temp; for (i=1; i =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=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Here, first, all elements that do not match the sort condition are shifted to the right, and then the current element is inserted into the free space.
Java code using while loop:
public static void insertionSort(int arr) { for(int i=1; i =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 swapped with them if necessary.
Estimated running time
Obviously, in the best case, the input of the algorithm will be an array already ordered in the right way. In this situation, the algorithm will simply have to check each element to make sure it is in the right place without making exchanges. Thus, the running time will directly depend on the length of the original array O(n).
The worst case input is an array sorted in reverse order. This will require a large number of permutations, the runtime function will depend on the number of elements squared.
The exact number of permutations for a completely unordered array can be calculated using the formula:
n(n-1)/2
where n is the length of the original array. Thus, it would take 4950 permutations to arrange 100 elements in the correct order.
The insertion method is very efficient for sorting small or partially sorted arrays. However, it is not recommended to apply it everywhere due to the high complexity of calculations.
The algorithm is used as an auxiliary in many other more complex sorting methods.
Sort equal values
The insertion algorithm belongs to the so-called stable sorts. It means,that it does not swap identical elements, but preserves their original order. The stability index is in many cases important for correct ordering.
The above is a great visual example of insertion sort in a dance.
