StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q51E

Expert-verifiedFound in: Page 204

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.

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

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}

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}

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.

94% of StudySmarter users get better grades.

Sign up for free