• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q51E

Expert-verified
Found in: Page 204

Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

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 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\ge 2$ )

For j : = 2 to n

i : = 1

While ${a}_{j}>{a}_{i}\phantom{\rule{0ex}{0ex}}i:=i+1\phantom{\rule{0ex}{0ex}}m:={a}_{j}$

For k = 0 to j - i - 1

${a}_{j-k}={a}_{j-k-1}\phantom{\rule{0ex}{0ex}}{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\ge 2$ )

For j : = 2 to n

i : = j - 1

While ${a}_{j}>{a}_{i}andi>0\phantom{\rule{0ex}{0ex}}i:=i-1\phantom{\rule{0ex}{0ex}}m:={a}_{j}$

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

${a}_{j-k}={a}_{j-k-1}\phantom{\rule{0ex}{0ex}}{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.