Chapter 2
Getting Started
Sun-Yuan Hsieh
謝孫源 教授
成功大學資訊工程學系
2.1 Insertion sort
Example: Sorting problem
Input: A sequence of n numbers a1, a2,…, an
Output: A permutation a1' , a2' ,..., an' of the input sequence
such that a1' a2' a. n'
The number that we wish to sort are known as the keys.
2
Pseudocode
Insertion sort
Insertion-sort(A)
1. for j 2 to length[A]
2. do key A[j]
3. *Insert A[j] into the sorted sequence A[1,…, j – 1]
4. ij–1
5. while i > 0 and A[i] > key
6. do A[i + 1] A[i]
7. ii–1
8. A[i + 1] key
3
The operation of Insertion-Sort
1 2 3 4 5 6 1 2 3 4 5 6
(a) 5 2 4 6 1 3 (b) 2 5 4 6 1 3
1 2 3 4 5 6 1 2 3 4 5 6
(c) 2 4 5 6 1 3 (d) 2 4 5 6 1 3
1 2 3 4 5 6 1 2 3 4 5 6
(e) 1 2 4 5 6 3 (f) 1 2 3 4 5 6
4
Sorted in place:
The numbers are rearranged within the array A, with at most a
constant number of them sorted outside the array at any time.
Loop invariant:
At the start of each iteration of the for loop of line 1-8, the
subarray A[1,…, j – 1] consists of the elements originally in
A[1,…, j – 1] but in sorted order.
5
2.2 Analyzing algorithms
Analyzing an algorithm has come to mean predicting the
resources that the algorithm requires.
Resources: memory, communication, bandwidth, logic gate,
time.
Assumption: one processor, RAM
constant-time instruction: arithmetic (add, subtract, multiply,
divide, remainder, floor, ceiling); data movement (load, store,
copy); control (conditional and unconditional bramch,
subroutine call and return)
Date type: integer and floating point
Limit on the size of each word of data
6
2.2 Analyzing algorithms
The best notion for input size depends on the problem
being studied.
The running time of an algorithm on a particular input
is the number of primitive operations or “steps” executed.
It is convenient to define the notion of step so that it is as
machine-independent as possible.
7
Analysis of insertion sort
Insertion-sort(A) cost cost
1. for j 2 to length[A] c1 n
2. do key A[j] c2 n–1
3. *Insert A[j] into the sorted
sequence A[1,…, j – 1] 0
4. ij–1 c4 n–1
n
5. while i > 0 and A[i] > key c5 t
j2 j
6. do A[i + 1] A[i] c6
n
j2
( t j 1)
7. ii–1 c7
n
j2
( t j 1)
8. A[i + 1] key c8 n–1
tj: the number of times the while loop test in line 5 is
executed for the value of j.
8
Analysis of insertion sort
The running time
T(n) = c1n + c2(n – 1) + c4(n – 1) + c5 n
t
j2 j + c6 n
j2
( t j 1)
+ c7 (t 1) + c8(n – 1)
n
j2 j
tj = 1, for j = 2, 3,…, n: Linear function on n
T(n) = c1n + c2(n – 1) + c4(n – 1) + c5(n – 1) + c8(n – 1)
= (c1 + c2 + c4 + c5 + c8)n – (c2 + c4 + c5 + c8)
9
Analysis of insertion sort
tj = j, for j = 2, 3,…, n: Quadratic function on n
n(n 1)
T(n) = c1n + c2(n – 1) + c4(n – 1) + c5 ( 1)
2
n(n 1) n(n 1)
+ c6 ( ) + c7 2 ) + c8(n – 1)
(
2
c5 c6 c7 2 c5 c6 c7
= (
2
) n – (c1 + c 2 + c4 + (
2
) + c8)n
– (c2 + c4 + c5 + c8)
10
Worst-case and average-case analysis
Usually, we concentrate on finding only on the worst-
case running time.
Reason:
It is an upper bound on the running time.
The worst case occurs fair often.
The average case is often as bad as the worst case. For example,
the insertion sort. Again, quadratic function.
11
Order of growth
In some particular cases, we shall be interested in
average-case, or expect running time of an algorithm.
It is the rate of growth, or order of growth, of the
running time that really interests us.
12
2.3 Designing algorithms
There are many ways to design algorithms:
Incremental approach: insertion sort
Divide-and-conquer: merge sort
recursive:
divide
conquer
combine
13
Pseudocode
Merge sort
Merge(A, p, q, r)
1. n1 q – p + 1
2. n2 r – q
3. create array L[1,…, n1 + 1] and R[1,…, n2 + 1]
4. for i 1 to n1
5. do L[i] A[p + i – 1]
6. for j 1 to n2
7. do R[j] A[q + j]
8. L[n1 + 1]
9. R[n2 + 1]
14
Pseudocode
10. i 1
11. j 1
12. for k p to r
13. do if L[i] R[j]
14. then A[k] L[i]
15. ii+1
16. else A[k] R[j]
17. jj+1
15
The operation of lines 10-17
8 9 10 11 12 13 14 15 16 17
A … 2 4 5 7 1 2 3 6 …
k
1 2 3 4 5 1 2 3 4 5
L 2 4 5 7 R 1 2 3 6
i j
(a)
16
The operation of lines 10-17
8 9 10 11 12 13 14 15 16 17
A … 1 4 5 7 1 2 3 6 …
k
1 2 3 4 5 1 2 3 4 5
L 2 4 5 7 R 1 2 3 6
i j
(b)
17
The operation of lines 10-17
8 9 10 11 12 13 14 15 16 17
A … 1 2 5 7 1 2 3 6 …
k
1 2 3 4 5 1 2 3 4 5
L 2 4 5 7 R 1 2 3 6
i j
(c)
18
The operation of lines 10-17
8 9 10 11 12 13 14 15 16 17
A … 1 2 2 7 1 2 3 6 …
k
1 2 3 4 5 1 2 3 4 5
L 2 4 5 7 R 1 2 3 6
i j
(d)
19
The operation of lines 10-17
8 9 10 11 12 13 14 15 16 17
A … 1 2 2 3 1 2 3 6 …
k
1 2 3 4 5 1 2 3 4 5
L 2 4 5 7 R 1 2 3 6
i j
(e)
20
The operation of lines 10-17
8 9 10 11 12 13 14 15 16 17
A … 1 2 2 3 4 2 3 6 …
k
1 2 3 4 5 1 2 3 4 5
L 2 4 5 7 R 1 2 3 6
i j
(f)
21
The operation of lines 10-17
8 9 10 11 12 13 14 15 16 17
A … 1 2 2 3 4 5 3 6 …
k
1 2 3 4 5 1 2 3 4 5
L 2 4 5 7 R 1 2 3 6
i j
(g)
22
The operation of lines 10-17
8 9 10 11 12 13 14 15 16 17
A … 1 2 2 3 4 5 6 6 …
k
1 2 3 4 5 1 2 3 4 5
L 2 4 5 7 R 1 2 3 6
i j
(h)
23
The operation of lines 10-17
8 9 10 11 12 13 14 15 16 17
A … 1 2 2 3 4 5 6 7 …
k
1 2 3 4 5 1 2 3 4 5
L 2 4 5 7 R 1 2 3 6
i j
(i)
24
Pseudocode
MERGE-SORT(A, p, r)
1. if p < r
2. then q (p + r)/2
3. MERGE-SORT(A, p, q)
4. MERGE-SORT(A, q + 1, r)
5. MERGE(A, p, q, r)
25
The operation of Merge sort
sorted
initial sequence
51 2 42 73 14 35 26 67
merge
52 24 45 7 1 3
2 23 6
merge merge
25 52 4 7 1 3 2 6
merge merge merge merge
5 2 4 7 1 3 2 6
26
Analysis of Merge sort
Analyzing divide-and-conquer algorithms
(1) if n c
T ( n)
aT (n / b) D(n) C (n) otherwise
See Chapter 4.
Analysis of merge sort
(1) if n 1
T ( n)
2T (n / 2) (n) if n 1
T(n) = (nlogn)
27
Analysis of Merge sort
c if n 1
T ( n)
2T (n / 2) cn if n 1
where the constant c represents the time require to solve problem
of size 1 as well as the time per array element of the divide and
combine steps.
28
The construction of a recursion tree
T(n)
(a)
cn cn
cn
c(n/2) c(n/2) cn
T(n/2) T(n/2) lg n
(b) c(n/4) c(n/4) c(n/4) c(n/4) cn
cn
c c c c c c c c cn
c(n/2) c(n/2)
n Total: cn lg n + cn
T(n/4) T(n/4) T(n/4) T(n/4) (d)
(c)
29
Outperforms insertion sort!
30
