Analysis of Algorithms : An Active Learning Approach

62 SORTING ALGORITHMS

By two applications of Equation 1.11, we get

Notice that by using Equations 1.9 and 1.10, we have

By applications of Equations 1.15, 1.14, 1.20, and the last formula, we get

3.1.3

1. Show the results of each pass of InsertionSort applied to the list [7, 3, 9,
   4, 2, 5, 6, 1, 8].


2. Show the results of each pass of InsertionSort applied to the list [3, 5, 2,
   9, 8, 1, 6, 4, 7].


3. Section 3.1.1 showed that a list in decreasing order leads to the worst case.
   This means that the list [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] would give the worst
   case of 45 comparisons. Find one other list of these 10 elements that will
   give the worst-case behavior. What more can you say generally about the
   class of input that generates the worst case for this algorithm.


4. When you look closely at the InsertionSort algorithm, you will notice
   that the insertion of a new element basically does a sequential search for the
   new location. We saw in Chapter 2 that binary searches are much faster.
   Consider a variation on insertion sort that does a binary search to find the

AN() 2 --i

i=1

N–1

∑^1

1

i=1i----------+^1

N–1

• ∑
  i=1

N–1

= +∑

1

i=1i----------+^1

N–1

∑

1

i=2--i

N

∑

1

i=1--i

N

∑



== – 1

AN()≈ 21 ------------------------()N– 21 N- +()N– 1 – ()lnN– 1

AN()N

(^2) – N
4
≈------------------+()N– 1 – ()lnN– 1
AN()N
(^2) + 3 N– 4
4
≈------------------------------–()lnN– 1
AN()N
2
≈------- 4
AN()= ON()^2
■3.1.3 EXERCISES