Search code examples
algorithmsortingpseudocode

Sorting Algorithm: Insertion sort - Pseudocode given in lectures seems wrong

I'm attending a basic class called Algorithms. We are studying the sorting algorithms; we were given the following pseudocode as an example of the insertion sort algorithm. However I think it's wrong.

For i in {2,..,n}:
    For j in {i,..,2}:
        If a(j)<a(j-1), swap a(j) and a(j-1)
        Else, Break

You can also see it here in the lecture notes, in this screenshot: insertion

I understand the first line - it starts from 2 because the first card is "already ordered", since it is the only card so far.

Is the second line a mistake? How can it be that we use j from i to 2? Of course this cannot hold true in the future. Also, shouldn't the break be less indented? So only one tab away instead of 2?

Edit

Here is the "main idea" of the algorithm. As you see the range of index j seems wrong from here. insertion2

Edit2 So here I try to write what happens in my mind, reading this pseudocode: Suppose I have the list (5,3,8,7,2,4,1,6). I will write | to separate the "hand" from the deck, also I'll write 5_ to emphasize which element I'm looking at. So here we go:

i = 1, (5|3,8,7,2,4,1,6)
i = 2, (5,3|8,7,2,4,1,6), now j in {2}, so we only have j = 2, a(j=2)=3 < a(j=1)=5, hence swap 3 with 5
i = 3, (3,5,8|7,2,4,1,6), j in {2,3}, so j=2 gives a(j=2)=5 !< a(j=1)=3 SO WE BREAK!
i = 4, (3,5,8,7|2,4,1,6), j in {2,3,4}, so j = 2 gives a(j=2)=5 !< a(j=1)=3, SO WE BREAK

and as you see this will always happen from now on because we start from 2 and because we break it! So even though the set of integers for j increases, we can't go further 2, because we just violate the condition

Solution

  • If you make the following assumptions, the code is valid:

    • An array of length N has indices 1..N
    • For loops cover the specified range regardless of the direction; thus, for x in {a,...,b} will go through a, a+1, a+2, ..., b-1, b if a <= b, but go through a, a-1, a-2, ..., b+1 b if a >= b.