CODEWITHSUNDEEP
algorithmsortingpseudocode
Euler_Salter
Euler_Salter

Reputation: 3561

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

Upvotes: 1

Views: 2162

Answers (2)

Scott Hunter
Scott Hunter

Reputation: 49803

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.

Upvotes: 3

夢のの夢
夢のの夢

Reputation: 5826

The second line isn't a mistake because you trying to take the i-th element(running on the outer loop) and insert into the partition before it. You then have to compare this element with the partition before it to make it sorted.

this SO post has a good visualization: Insertion Sort vs. Selection Sort

Upvotes: 2

Related Questions