# Homework Help: Number of comparisons in an insertion sort

1. Dec 10, 2012

### nicnicman

1. The problem statement, all variables and given/known data
How many comparisons does the insertion sort use to sort the list n, n-1, ......2, 1?

2. Relevant equations

3. The attempt at a solution
Insertion sort compares every element with every other element in the list, but I'm unsure what this question is asking. Why does it jump from n, n-1 to 2, 1?

Thanks for any suggestions.

2. Dec 10, 2012

### phinds

What jump? Do you not understand what the ellipsis stands for ?

3. Dec 10, 2012

### nicnicman

Yes, but usually there is an order like 1, 2, . . . , n. I guess I just don't see the order here.

4. Dec 10, 2012

### phinds

SO you feel that 1, 2, ... n is ordered but the reverse is not?

5. Dec 10, 2012

### Staff: Mentor

n, n-1, ......2, 1 means the list in reversed order. After the sort routine is finished, the order will be 1, 2, 3, ..., n - 1, n

6. Dec 10, 2012

### nicnicman

Oh, okay. I see now. Thanks.

7. Dec 10, 2012

### nicnicman

So would the answer be n - 1?

8. Dec 10, 2012

### nicnicman

Never mind it would be n - 1 passes, not comparisons.

9. Dec 10, 2012

### nicnicman

Actually, after thinking about a bit more, wouldn't the insertion sort also make n - 1 comparisons since the list is already in descending order.

Sorry for all the posts.

10. Dec 10, 2012

### Staff: Mentor

But you want the list to be in ascending order, right?

11. Dec 10, 2012

### nicnicman

Right. So, if you had a list 3, 2, 1 the comparisons would go like this:

Comparison 1. compare 2 and 3, we have 2, 3, 1
Comparison 2. compare 1 and 2 , we have 1, 2, 3

Done, with 2 comparisons, or n - 1.

Please, correct me if I'm wrong.

Last edited: Dec 10, 2012
12. Dec 11, 2012

### nicnicman

I'm still not entirely sure of my answer and I was hoping someone would offer some advice.

Thanks for any suggestions.

13. Dec 11, 2012

### Staff: Mentor

Your list is too short to really give you any insight. How about if the list is 5, 4, 3, 2, 1?

14. Dec 11, 2012

### nicnicman

That was the exact list I tried it with first. I only used a smaller list here for simplification. Anyway, with the longer list I got the same results: n-1.

15. Dec 11, 2012

### Staff: Mentor

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook