Suggested languages for you:

Americas

Europe

Q48E

Expert-verified
Found in: Page 203

### Discrete Mathematics and its Applications

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 .

See the step by step solution

## Step 1:

• 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

## Step 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 .

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 .

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 .

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 .

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 .

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 .

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

## Step 3:

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 .

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 .

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 .

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 .

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 .

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 .

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