insertion sort in Introduction to Algorithm

Question

in an Introduction to Algorithm 2nd edition, I found insertion sort pseudo code

INSERTION-SORT(A)
1   for j <- 2 to length[A]
2       do key <- A[j]
3          //Insert A[j] into the sorted sequence A[1 □ j - 1].
4          i <- j - 1
5          while i > 0 and A[i] > key
6           do A[i+1] <- A[i]
7              i <- i -1
8          A[i + 1] <- key

but I can't understand how swap works here.

I think it needs a swap operation like this

INSERTION-SORT(A)
1   for j <- 2 to length[A]
2       do key <- A[j]
3          //Insert A[j] into the sorted sequence A[1 □ j - 1].
4          i <- j - 1
5          while i > 0 and A[i] > key
6           do temp <- A[i+1]
7              A[i+1] <- A[i]
8              A[i] <- temp
9              i <- i -1
10         A[i + 1] <- key

did I get something wrong? please help

Answer 1

What's happening in insertion sort is not a swap.

It is moving each item greater than the one you want to insert up by one index working down from the end of the currently sorted section, and then inserting the new record at the correct place after the old value is moved up.

Answer 2

but I can't understand how swap works here.

No it does not.

The value is already saved in the beggining.

It saves j and then shifts all the other elements until it finds the proper place

Answer 3

I experience the same problem. Below is the code in C which implements the above pseudo-code correctly.

The tricky part about this was that the pseudo code is using 1-based array notations unlike most programming languages!

#include <stdio.h>

int main(void)
{
  int A[] = { 50, 20, 10, 40, 60, 30 };
  int j, key, len, i;
  len = (sizeof(A)) / (sizeof(A[0]));

    for (j = 1; j < 6; j++) {  <-- Change here
      key = A[j];
      // Insert key into the sorted sequence A[1 .. j - 1].
      i = j - 1;
      while (i >= 0 && A[i] > key) {  <-- Change here
          A[i + 1] = A[i];
          i--;
      }
      A[i + 1] = key;
    }

    for (int z = 0; z < len; z++) {
       printf("%d ", A[z]);
    }
   printf("\n");
 }

Answer 4

The code is doing a "multi-swap", more precisely a rotation of a k elements by one position, in-place. This takes a single auxiliary key variable, like a swap does.