Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Short Answer

When a list of elements is in close to the correct order, would it be better to use an insertion sort or its variation described in Exercise 50?

Hence, it is concluded that the changed insertion sort algorithm will work nicely if the list is close to the correct order.

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step 1:

Insertion sort Algorithm: the insertion sort compares this second element with the first element and inserts it before the first element if it does not exceed the first element hence the first two elements are in the correct order.
Then, the third element is compared with the first element and if it is larger than the first element it is compared with the second element, and this is inserted on the correct position among the first three elements. Hence, we will continue this procedure till the sort is complete.
Now, see both the algorithm one by one.

Step 2:

Now, the required insertion sort algorithm is:

Procedure insertionsort ( $a_{1}, a_{2}, . . ., a_{n} :$ : real numbers, $n \geq 2$ )

For j : = 2 to n

i : = 1

While $a_{j} > a_{i} i : = i + 1 m : = a_{j}$

For k = 0 to j - i - 1

$a_{j - k} = a_{j - k - 1} a_{i} : = m$

{ $a_{1}, a_{2}, . . ., a_{n}$ is in increasing order}

Step 3:

Now, see the changed insertion sort algorithm:

Procedure insertionsort ( $a_{1}, a_{2}, . . . ., a_{n} :$ : real numbers, $n \geq 2$ )

For j : = 2 to n

i : = j - 1

While $a_{j} > a_{i} a n d i > 0 i : = i - 1 m : = a_{j}$

For k = 0 to j - i - 1 to 0

$a_{j - k} = a_{j - k - 1} a_{i} : = m$

{ $a_{1}, a_{2}, . . ., a_{n}$ is in increasing order}

Step 4:

So, from the above two algorithm its is concluded that the use of linear search at the time of insertion of element will make the process fast if the elements are close to the correct order and the reason behind the statement is that the linear search goes from back to front.

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

When a list of elements is in close to the correct order, would it be better to use an insertion sort or its variation described in Exercise 50?

Step by Step Solution

Step 1:

Step 2:

Step 3:

Step 4:

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

When a list of elements is in close to the correct order, would it be better to use an insertion sort or its variation described in Exercise 50?

Step by Step Solution

Step 1:

Step 2:

Step 3:

Step 4:

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths