# Comparisons in Insertion Sort

Discussion in 'Homework Help' started by zulfi100, Jan 2, 2016.

1. ### zulfi100 Thread Starter Member

Jun 7, 2012
320
0
Hi,
I cant understand the above statement. I have attached an example & by looking at that i cant understand how we have L/2 comparisons

The algorithm for Insertion sort is:

Some body please guide me with this comparison problem.

Zulfi.

File size:
2.6 MB
Views:
4
2. ### WBahn Moderator

Mar 31, 2012
18,089
4,917
First, let's use the variable S to represent the number of values in the list that have to be shifted in order to insert the last element into its proper place.

In other words, consider the following list in which we want to insert the last element into its proper place.

1 2 4 5 6 7 8 9 3

S, in this case, would be 6

Figure out how many comparisons and assignments are required to move the 3 into its final position in terms of S.

The only remaining question is what the value of S is, on average. Sometimes it will be 0 (though you will always have at least one comparison to make) and sometimes it will be L (the entire list has to be shifted). But, on average, what do you expect it to be? This is assuming that the list being sorted is effectively random.

3. ### WBahn Moderator

Mar 31, 2012
18,089
4,917
Oh, and surely you could get that monster attachment down to a much more reasonable size, couldn't you?

absf likes this.
4. ### zulfi100 Thread Starter Member

Jun 7, 2012
320
0
Hi,

Thanks for your reply. I have got some confusion. S represents number of shifts. To insert 3 at its proper place there would be 6 shifts (fine, as you say). But comparisons would be more. If you look at the algorithm, loop starts at line#2. But comparisons are starting from line#3. So first comparison would be:

2 < 1 (false: no shifting) then

4 < 2 (false: no sifting) then

5 < 4 (false: no shifting) then

6 < 5 (false: no shifting) then

7 < 6 (false: no shifting) then

8 < 7 (false: no shifting) then

9 < 8 (false: no shifting) then

3 < 9 (true: first shifting occurs & marker2 comes into play)

Now we will execute the loop starting at line#4. There would be shifting i.e 6 & again comparisons probably 6, so altogether 13 comparisons. Am I right, please guide me?

Zulfi.

5. ### WBahn Moderator

Mar 31, 2012
18,089
4,917
Look at the algorithm more closely. You start at the other end.

0 1 2 3 4 5 6 7 8 (index)
1 2 4 5 6 7 8 9 3 (value)

v[7] < v[8] ? = True => temp = 3, v[8] = v[7]
v[6] < temp ? = True => v[7] = v[6]
v[5] < temp ? = True => v[6] = v[5]
v[4] < temp ? = True => v[5] = v[4]
v[3] < temp ? = True => v[4] = v[3]
v[2] < temp ? = True => v[3] = v[2]
v[1] < temp? = False => v[2] = temp

Remember, the question is asking about the number of operations needed to move the last element in the list (which is the item that Marker1 is currently pointing to) into its proper location. That means that the algorithm has already been run long enough to make it so that everything but the last element is already sorted.

6. ### zulfi100 Thread Starter Member

Jun 7, 2012
320
0
Hi,
0 1 2 3 4 5 6 7 8 (index)
1 2 4 5 6 7 8 9 3 (value)

v[7] < v[8] ? = True => temp = 3, v[8] = v[7]c

Sorry my teacher:
v[7] = 9
v[8] = 3
9<3?= False???

Any way I accept that there would be 6 comparison. But on the average how it can be L/2??

Zulfi.

7. ### WBahn Moderator

Mar 31, 2012
18,089
4,917
Consider all of the possible cases.

How many comparisons will there be if the final value is already in its final position?

How many will there be when it only has to be moved back one place? Two places? Three? All but one? All the way to the first?

What's the average?

8. ### zulfi100 Thread Starter Member

Jun 7, 2012
320
0
final pos = 1
one place = 2
two place = 3
three place = 4
four place = 5
five place = 6
six place = 7
seven place = 8
eight place = 9
nine place = 10
avg = 55/9 = 6.11
where as n/2 = 4.5

So what's wrong here?

Zulfi.

9. ### WBahn Moderator

Mar 31, 2012
18,089
4,917
On thing that you are forgetting is that these analyses are asymptotic for large values of n, so you are looking at what they converge to, not what their exact values are.

Jun 7, 2012
320
0
Okay thanks.

Zulfi.