In this section, we consider an application of the decrease-by-one technique to sorting an array A[0..n − 1]. Following the technique’s idea, we assume that the smaller problem of sorting the array A[0..n − 2] has already been solved to give us a sorted array of size n − 1: A[0] ≤ . . . ≤ A[n − 2].

**Insertion
Sort**

In this
section, we consider an application of the decrease-by-one technique to sorting
an array ** A**[0

Though
insertion sort is clearly based on a recursive idea, it is more efficient to
implement this algorithm bottom up, i.e., iteratively. As shown in Figure 4.3,
starting with ** A**[1] and
ending with

Here is
pseudocode of this algorithm.

**ALGORITHM** *InsertionSort*** (A**[0

//Sorts a
given array by insertion sort

//Input:
An array ** A**[0

** v **←

**while ***j*** **≥** **0** and **** A**[

** A**[

** A**[

The
operation of the algorithm is illustrated in Figure 4.4.

The basic
operation of the algorithm is the key comparison ** A**[

The
number of key comparisons in this algorithm obviously depends on the nature of
the input. In the worst case, ** A**[

Thus, in
the worst case, insertion sort makes exactly the same number of compar-isons as
selection sort (see Section 3.1).

In the
best case, the comparison ** A**[

This very
good performance in the best case of sorted arrays is not very useful by
itself, because we cannot expect such convenient inputs. However, almost-sorted
files do arise in a variety of applications, and insertion sort preserves its
excellent performance on such inputs.

A
rigorous analysis of the algorithm’s average-case efficiency is based on
investigating the number of element pairs that are out of order (see Problem 11
in this section’s exercises). It shows that on randomly ordered arrays,
insertion sort makes on average half as many comparisons as on decreasing
arrays, i.e.,

This
twice-as-fast average-case performance coupled with an excellent efficiency on
almost-sorted arrays makes insertion sort stand out among its principal
com-petitors among elementary sorting algorithms, selection sort and bubble
sort. In addition, its extension named ** shellsort**, after its inventor D. L.
Shell [She59], gives us an even better algorithm for sorting moderately large
files (see Problem 12 in this section’s exercises).

**Exercises
4.1**

1. *Ferrying soldiers *A
detachment of* **n** *soldiers
must cross a wide and deep* *river with
no bridge in sight. They notice two 12-year-old boys playing in a rowboat by
the shore. The boat is so tiny, however, that it can only hold two boys or one
soldier. How can the soldiers get across the river and leave the boys in joint
possession of the boat? How many times need the boat pass from shore to shore?

**2. ***Alternating
glasses*

**
**There are 2** n** glasses
standing next to each other in a row, the first

**
**Solve the same problem if 2** n** glasses—

3. *Marking cells *Design an algorithm for the
following task. For any even* **n,** *mark ** n** cells on an infinite sheet of
graph paper so that each marked cell has an odd number of marked neighbors. Two
cells are considered neighbors if they are next to each other either
horizontally or vertically but not diagonally. The marked cells must form a
contiguous region, i.e., a region in which there is a path between any pair of
marked cells that goes through a sequence of marked neighbors. [Kor05]

4. Design a decrease-by-one algorithm for generating
the power set of a set of ** n**
elements. (The power set of a set

5. Consider the following algorithm to check
connectivity of a graph defined by its adjacency matrix.

**ALGORITHM** *Connected*** (A**[0

//Input:
Adjacency matrix ** A**[0

**if ***n*** **=** **1** return **1 //one-vertex graph
is connected by definition

**else**

**if not ***Connected*** (A**[0

**if **** A**[

Does this
algorithm work correctly for every undirected graph with ** n >** 0 vertices? If you answer yes,
indicate the algorithm’s efficiency class in the worst case; if you answer no,
explain why.

7. **
***Team
ordering *You have the results of a completed round-robin tournament* *in which ** n** teams
played each other once. Each game ended either with a victory for one of the
teams or with a tie. Design an algorithm that lists the teams in a sequence so
that every team did not lose the game with the team listed immediately after
it. What is the time efficiency class of your algorithm?

8. Apply insertion sort to sort the list ** E, X, A**,

**
****a. **What
sentinel should be put before the first element of an array being** **sorted in order to avoid checking the
in-bound condition ** j** ≥ 0 on each iteration of the inner
loop of insertion sort?

**b. **Is the sentinel version in the
same efficiency class as the original version?

9. Is it possible to implement insertion sort for
sorting linked lists? Will it have the same ** O**(

10. Compare the text’s implementation of insertion sort
with the following ver-sion.

**ALGORITHM** *InsertSort2*** (A**[0

**for ***i*** **←** **1** to ***n*** **−** **1** do **** j **←

**while ***j*** **≥** **0** and **** A**[

** j **←

What is
the time efficiency of this algorithm? How is it compared to that of the
version given in Section 4.1?

11. Let ** A**[0

**
**What arrays of size ** n** have the
largest number of inversions and what is this number? Answer the same questions
for the smallest number of inversions.

**
**Show that the average-case number of key
comparisons in insertion sort is given by the formula

12. Shellsort (more accurately Shell’s sort) is an
important sorting algorithm that works by applying insertion sort to each of
several interleaving sublists of a given list. On each pass through the list,
the sublists in question are formed by stepping through the list with an
increment ** h_{i}** taken
from some predefined decreasing sequence of step sizes,

**a. **Apply
shellsort to the list

*S, H, E, L, L, S, O, R, T , I, S, U, S, E, F, U,
L*

**
**Is shellsort a stable sorting algorithm?

**
**Implement shellsort, straight insertion sort,
selection sort, and bubble sort in the language of your choice and compare
their performance on random arrays of sizes 10**^{n}** for

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Decrease and Conquer : Insertion Sort |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.