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

For understanding, it helps to trace things out on paper, line by line, and keep track of the variables and the array on every line. — saner
– saner, Commented Nov 11, 2019 at 13:21

Don Roby · Accepted Answer · 2012-01-25 20:59:14Z

2

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.

answered Jan 25, 2012 at 20:59

Don Roby

41.2k6 gold badges95 silver badges114 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Cratylus · Accepted Answer · 2012-01-25 21:02:11Z

1

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

answered Jan 25, 2012 at 21:02

Cratylus

54.3k73 gold badges222 silver badges348 bronze badges

Comments

user1196549 · Accepted Answer · 2017-12-31 16:41:45Z

1

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.

answered Dec 31, 2017 at 16:41

user1196549

Comments

rrz0 · Accepted Answer · 2017-12-31 16:34:41Z

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");
 }

Collectives™ on Stack Overflow

insertion sort in Introduction to Algorithm

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related