Number of comparisons in an insertion sort

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.

phinds

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

nicnicman

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

phinds

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

Mark44

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

nicnicman

Oh, okay. I see now. Thanks.

nicnicman

So would the answer be n - 1?

nicnicman

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

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.

Mark44

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

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.

nicnicman

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

Thanks for any suggestions.

Mark44

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

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.

Mark44

Take a look at this wiki page: http://en.wikipedia.org/wiki/Insertion_sort