Searching the internet shows an example of ordering this code:
int i, pos, aux;
for (i = 0; i<5; i++) {
pos = i;
aux = notas[i];
while ((pos>0) && (aux < notas[pos - 1])) {
notas[pos] = notas[pos -1];
pos--;
}
notas[pos] = aux;
}
and it works correctly, but I don't understand why it is thought like this specifically when instead of doing an exchange of values what it does is copy the value of the previous position and continue copying the previous position while it is smaller and at the end put the original value that it had been stored in an auxiliary.
I don't understand why that copy instead of using an exchange of values and thus forget about the auxiliary variable that is left out of the while (although in the exchange of values it should use an auxiliary one as well, but it is at the moment itself, what it does more understandable to the code).
Is there a reason that perhaps escapes me?
The insertion algorithm is intuitive and easy to understand (not exactly the most efficient) and can be useful for ordering a set of cards when we have them in our hands.
You have to do as many "iterations" as there are cards in your hands. In each iteration
i
it is about moving thei
-th card as far to the left as possible, so that thei
first cards are ordered at the end of that iteration.Thus, in the first iteration we "move" the first card as far to the left as possible. That is, we do nothing in this case because it is already on the left at all. In fact we could skip this first iteration.
In the next iteration we take the second card and compare it with the one to its left. If the one we have taken is smaller, we move it if we don't leave it there. In the following iterations we take the corresponding card and we compare it with all the ones to its left, one by one. As long as the one we have taken is smaller, we continue comparing, until we reach one that is smaller than it and in that place we insert it and go to the next iteration. After the last iteration they will all be sorted.
If you notice, however, when doing the sorting in the hand, in each iteration that we move a card from its original place to its leftmost "right place," in order to make that move we are moving all the cards to the right. cards that were between your starting position and your destination position. That is why it is necessary to copy in each element of the array what was in its previous position, to "make room" in the place where it is going to be placed.
I don't know if what you propose (to use an auxiliary inside the loop) would be this:
Effectively this algorithm is equivalent, but it is slightly more inefficient as it has more assignments inside the loop. The total number of executed mappings is higher in this implementation.
Extra
This animation (taken from brilliant.org , where it also explains other sorting algorithms) perfectly shows how insertion sort works: