Suggested languages for you:

Americas

Europe

Q48E

Expert-verifiedFound in: Page 203

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**Compare the number of comparisons used by the insertion sort and the binary insertion sort to sort the list 7, 4, 3, 8, 1, 5, 4, 2.**

Hence, The number of comparisons in insertion sort is whereas the number of comparisons in binary insertion sort is and the given array 7,4,3,8,15,4,2 became 1,2,3,4,4,5,7,8 .

- first find the number of comparisons done by the insertion sort.
- Then find the number of comparisons done by the binary sort.
- After completion compare the number of comparisons done by both of these algorithms.
- The list to be short is 7,4,3,8,1,5,4,2

In the case of insertion sort:

Case 1:

Compare the first two elements in this case.

Since 7 > 4 so 4 is inserted before the 7 .

Number of comparisons done: 1

4,7,3,8,1,5,4,2

Case 2:

Compare the third element with the elements before it.

Since 3 < 4 so inserted 3 before 4 .

Number of comparisons made: 1

3,4,7,8,1,5,4,2

Case 3:

Now, compare the fourth element in this case with the sorted arrays before it.

Since ,$8>3\phantom{\rule{0ex}{0ex}}8>4\phantom{\rule{0ex}{0ex}}and8>7$

so, insert 8 after 7 .

Number of comparisons made: 3

3,4,7,8,1,5,4,2

Case 4:

Now, compare the fifth element in this case with the sorted arrays before it.

Since 1 < 3 so insert before 3 .

Number of comparisons made: 1

1,3,4,7,8,5,4,2

Case 5:

Now, compare the sixth element in this case with the sorted arrays before it.

Since $5>1\phantom{\rule{0ex}{0ex}}5>3\phantom{\rule{0ex}{0ex}}5>4\phantom{\rule{0ex}{0ex}}and5<7$

so, insert 5 between 4 and 7 .

Number of comparisons made: 4

1,3,4,5,7,8,4,2

Case 6

Now, compare the seventh element in this case with the sorted arrays before it.

Since $4>1\phantom{\rule{0ex}{0ex}}4>3\phantom{\rule{0ex}{0ex}}and4=4$

So, inserted 4 after 3 and before the previous 4 .

Number of comparisons made: 3

1,3,4,4,5,7,8,2

Case 7:

Now, compare the eighth element in this case with the sorted arrays before it.

Since $2>1\phantom{\rule{0ex}{0ex}}and2<3$

So, insert 2 between 1 and 3 .

Number of comparisons made: 2

1,2,3,4,4,5,7,8

Thus, the total number of comparisons in Insertion Sort is:

1+1+3+1+4+3+2 = 15

In the case of binary insertion sort:

Case 1:

First, compare the first two elements in this case.

Since 7 > 4 so is inserted before the 7 .

Number of comparisons done: 1

4,7,3,8,1,5,4,2

Case 2:

Compare the third element with the elements before it.

Since 3 < 4 so inserted 3 before 4 .

Number of comparisons made: 1

3,4,7,8,1,5,4,2

Case 3:

Now, compare the fourth element in this case with the sorted arrays before it.

Since 8 > 4

and 8 > 7

so, insert 8 after 7 .

Number of comparisons made: 2

3,4,7,8,1,5,4,2

Case 4:

Now, compare the fifth element in this case with the sorted arrays before it.

Since 1 < 4 so insert 1 before 4 .

Then compare 1 with the first element 3 .

Since 1 < 3 so insert 1 before 3 .

Number of comparisons made: 2

1,3,4,7,8,5,4,2

Case 5:

Now, compare the sixth element in this case with the sorted arrays before it.

Since 5 > 4

and 5 < 7

so, insert between 4 and 7 .

Number of comparisons made: 2

1,3,4,5,7,8,4,2

Case 6

Now, compare the seventh element in this case with the sorted arrays before it.

Since $4>1\phantom{\rule{0ex}{0ex}}4>3\phantom{\rule{0ex}{0ex}}and4=4$

So, inserted 4 after 3 and before the previous 4 .

Number of comparisons made:

1,3,4,4,5,7,8,2

Case 7:

Now, compare the eighth element in this case with the sorted arrays before it.

Since $2>1\phantom{\rule{0ex}{0ex}}2<3\phantom{\rule{0ex}{0ex}}and2<4$

So, insert between 1 and 3 .

Number of comparisons made: 2

1,2,3,4,4,5,7,8

Thus, the total number of comparisons in Insertion Sort is:

1+1+2+2+2+3+2 = 13

94% of StudySmarter users get better grades.

Sign up for free