How to understand changing key value in insertion sort?

Question

I know what insertion sort is but I don't understand the code. And I searched it is all explanation about the sort but not the code. It will be easier for me if you answer the question step by step with examples! Thanks! Use this code for example. I put my questions in comment to make it clearer.

void insertionSort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i-1;

       while (j >= 0 && arr[j] > key)
       {
           arr[j+1] = arr[j];
 /* if arr[j] > key, at here arr[j+1] has the number in arr[j] which is i
  * or key right? But now only arr[j+1] changed. There are only two same
  * numbers which is the bigger number, arr[j] is not changed to the smaller
  * number which arr[j+1] was.
  */
           j = j-1;
       }
       arr[j+1] = key;    
 /* so at here arr[j+1] now has the value of key which is arr[i], so the 
  * sorted arr[j+1] ended up unchanged? I know this step is supposed to 
  * change key to use it to compare numbers after.
  */
   }
}

Answer 1

Your questions are a bit unclear, so let me try to explain what happens in the code, before attempting to answer them

• The outer loop variable i, represents the start of the unsorted data in the array. It will be incremented from 1 to n through the for loop
• key represents the first element from the unsorted region, which we are attempting to put in the correct spot after the while loop finishes
• j represents the last index in the sorted region. It will be decremented to 0 through the while loop

The basic idea is to insert the next element in the unsorted part, by right shifting required elements from the sorted part till the final position of this new element

Now to your questions

if arr[j] > key, at here arr[j+1] has the number in arr[j]

YES

which is i or key right?

NO. arr[j+1] == key, only during the first iteration of the while, not after that

But now only arr[j+1] changed.

Yes and No. In one iteration of the loop, only arr[j+1] changed, but in the next iteration when j = j -1, the previous element changes or rather is shifted right

There are only two same numbers which is the bigger number, arr[j] is not changed to the smaller number which arr[j+1] was.

In a given iteration arr[j] does not change, but that does not mean that arr[j] does not change in the next iteration. For example, let's say j = 10 is the current iteration. so a[10] does not change in this iteration of the while loop, but it might change in the next iteration when j = 9 and a[10] = a[9]

so at here arr[j+1] now has the value of key which is arr[i]

No, arr[i] is potentially overwritten by the first iteration of the while loop, and hence was backed up in key

so the sorted arr[j+1] ended up unchanged? I know this step is supposed to change key to use it to compare numbers after.

This is invalid based on the above answer