# Number of comparisons in an insertion sort

by nicnicman
Tags: comparisons, insertion, number, sort
 P: 136 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.
PF Gold
P: 6,486
 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 ?
 P: 136 Yes, but usually there is an order like 1, 2, . . . , n. I guess I just don't see the order here.
 PF Gold P: 6,486 Number of comparisons in an insertion sort SO you feel that 1, 2, ... n is ordered but the reverse is not?
 Mentor P: 21,397 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
 P: 136 Oh, okay. I see now. Thanks.
 P: 136 So would the answer be n - 1?
 P: 136 Never mind it would be n - 1 passes, not comparisons.
 P: 136 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
P: 21,397
 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?
 P: 136 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.
 P: 136 I'm still not entirely sure of my answer and I was hoping someone would offer some advice. Thanks for any suggestions.
Mentor
P: 21,397
 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?
 P: 136 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 P: 21,397 Take a look at this wiki page: http://en.wikipedia.org/wiki/Insertion_sort

 Related Discussions 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