1

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

Improve this question
5
  • This is pseudocode, so there's no way of telling, what the step direction is in a For loop... you can see that the code is right, if in the second For the step size is -1. However, without any introductions that's pretty ambiguous pseudocode. After your edit, it is clear that you want to step backwards in the second loop. Commented Feb 9, 2017 at 16:00
  • @BeyelerStudios, I thought about a negative step. However it still wouldn't work. Because whenever you "add a new card to the hand", you need to check this card with every other card in the hand, not only from the second! Commented Feb 9, 2017 at 16:03
  • Also, each time you insert a card, you waste time because you have to check again all the cards that you have already checked. The $2$ is surely a mistake Commented Feb 9, 2017 at 16:13
  • @BeyelerStudios, okay, but then how do you explain what happens in my example in the new edit? Commented Feb 9, 2017 at 16:25
  • 1
    @BeyelerStudios oh okay that makes sense now! Commented Feb 9, 2017 at 16:29

2 Answers 2

Reset to default
3

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.
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

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

Improve this answer

4 Comments

sorry I don't understand what you mean by "outter loop" and "partition before it".
as the name implies, you insert an element to a already sorted list. This is why you always start with the second element in the array, because the first element is already sorted. So I meant by 'partition before it' in this case is just the first element.
but starting from 2 and arriving to i, is it not just an immense repetition of actions? Each time you insert a new element in the list, you check each element in the list again with the one next to it, which you already did before
Yes. It's why insertion sort has the worst case of N^2. And you check the element you trying to insert with the 'sorted list'. So let's say you are inserting the i-th element, you want to compare and swap with i-1th element, and then i-2th, and so on, until you make list sorted again.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.