## Number of comparisons in an insertion sort

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.
 PhysOrg.com science news on PhysOrg.com >> New language discovery reveals linguistic insights>> US official: Solar plane to help ground energy use (Update)>> Four microphones, computer algorithm enough to produce 3-D model of simple, convex room

Recognitions:
Gold Member
 Quote by 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.
What jump? Do you not understand what the ellipsis stands for ?
 Yes, but usually there is an order like 1, 2, . . . , n. I guess I just don't see the order here.

Recognitions:
Gold Member

## Number of comparisons in an insertion sort

SO you feel that 1, 2, ... n is ordered but the reverse is not?
 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
 Oh, okay. I see now. Thanks.
 So would the answer be n - 1?
 Never mind it would be n - 1 passes, not comparisons.
 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.

Mentor
 Quote by 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.
But you want the list to be in ascending order, right?
 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.
 I'm still not entirely sure of my answer and I was hoping someone would offer some advice. Thanks for any suggestions.

Mentor
 Quote by 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.
Your list is too short to really give you any insight. How about if the list is 5, 4, 3, 2, 1?
 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.
 Mentor Take a look at this wiki page: http://en.wikipedia.org/wiki/Insertion_sort

 Similar discussions for: Number of comparisons in an insertion sort Thread Forum Replies Engineering, Comp Sci, & Technology Homework 3 Engineering, Comp Sci, & Technology Homework 0 Engineering, Comp Sci, & Technology Homework 1 Linear & Abstract Algebra 34 Engineering, Comp Sci, & Technology Homework 0