Number of comparisons in an insertion sort

[nicnicman]

Homework Statement

How many comparisons does the insertion sort use to sort the list n, n-1, ...2, 1?

Homework Equations

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]

Homework Statement

How many comparisons does the insertion sort use to sort the list n, n-1, ...2, 1?

Homework Equations

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 ?

 

[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]

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?

 

[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]

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?

 

[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