Lectures 1-2.

Introduction - Insertion Sort - Merge Sort

Introduction to Algorithms
Da Nang University of Science and Technology

Dang Thien Binh

dtbinh@dut.udn.vn

IT Faculty Copyright
Dang2000-2022
Thien Binh
IT Faculty
1/28
Algorithm

 A well-defined computational procedure that

transforms the input to the output
 Describes a specific computational procedure for
achieving the desired input/output relationship
 An instance of a problem is all the inputs needed
to compute a solution to the problem
 A correct algorithm
 halts with the correct output for every input instance
 is said to solve the problem

IT Faculty Dang Thien Binh 2/28

Algorithm

 Example: Sorting
 Input: A sequence of n numbers <a1, a2, ..., an>
 Output: A permutation (reordering) <b1, b2, ..., bn> of the
input sequence such that 𝑏1 ≤ 𝑏2 ≤ ⋯ ≤ 𝑏𝑛
 Instance: <6, 4, 3, 7, 1, 4>

IT Faculty Dang Thien Binh 3/28

Algorithm

 Insertion Sort
 In-place sorting: Uses only a fixed amount of storage
beyond that needed for the data
 Example:
 643714 46 3714
^* ^ *
346714 34 6714
* ^ *
134674 13 4467
^ *

IT Faculty Dang Thien Binh 4/28

Algorithm

 Example: 6 4 3 7 1 4

6 4 3 7 1 4

IT Faculty Dang Thien Binh 5/28

Algorithm

 Pseudocode:
INSERTION-SORT(A) /* A is an array of numbers */
1 for j  2 to length[A]
2 key  A[j]
3 /* insert A[j] into the sorted sequence A[1 .. j-1] */
4 ij-1
5 while i > 0 and A[i] > key
6 A[i+1]  A[i]
7 ii-1
8 A[i+1]  key

IT Faculty Dang Thien Binh 6/28

Algorithm

IT Faculty Dang Thien Binh 7/28

Algorithm

 Example:
 5 2 4 6 1 3

IT Faculty Dang Thien Binh 8/28

Insertion Sort Algorithm

 Video Content
 An illustration of Insertion Sort with Romanian folk dance.

IT Faculty Dang Thien Binh 9/28

Insertion Sort Algorithm

IT Faculty Dang Thien Binh 10/28

Analyzing Algorithm

 Predicting the resources, such as memory, bandwidth,

logic gates, or running time
 Assumed implementation model
 Random-access machine (RAM)
 Running time: f(input size)
 Input size:
 Sorting: number of items to be sorted.
 Multiplication: number of bits.
 Graphs: numbers of vertices and edges.

IT Faculty Dang Thien Binh 11/28

 Analyzing Algorithm

 Running time for a particular input is the number of

primitive operations executed
 Assumption: Constant time ci for the execution of the
ith line (of pseudocode)

Note: tj is the number of times the while loop test in line 5 is executed for the value of j.
IT Faculty Dang Thien Binh 12/28
Analyzing Algorithm

IT Faculty Dang Thien Binh 13/28

Analyzing Algorithm

 Best case
 Array is already sorted, so tj = 1 for j = 2, 3, ..., 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)
= an + b (linear in n)
 Worst case


= an2 + bn + c (quadratic in n).

IT Faculty Dang Thien Binh 14/28

Analyzing Algorithm

 Average Case?
 Concentrate on worst-case running time
 Provides the upper bound
 Occurs often
 Average case is often as bad as the worst case
 Order of Growth
 The order of a running-time function is the fastest growing
term, discarding constant factors
 Insertion sort
 Best case: an + b → (n)
 Worst case: an2 + bn + c → (n2)

IT Faculty Dang Thien Binh 15/28

Designing Algorithms

 Incremental design
 Iterative
 Example: insertion sort
 Divide-and-conquer algorithm
 Recursive
 Example: merge sort
 Three steps in the divide-and-conquer paradigm
 Divide the problem into smaller subproblems
 Conquer subproblems by solving them recursively
 Combine solutions of subproblems

IT Faculty Dang Thien Binh 16/28

Designing Algorithms

 Merge Sort
 Divide the n-element sequence into two subsequences of n/2
elements each
 Conquer (sort) the two subsequences recursively using merge
sort
 Combine (merge) the two sorted subsequences to produce
the sorted answer
 Note: Recursion bottoms out when only one element
to be sorted

IT Faculty Dang Thien Binh 17/28

Divide ...

5 1 4 2 10 3 9 15

5 1 4 2 10 3 9 15

5 1 4 2 10 3 9 15

5 1 4 2 10 3 9 15

IT Faculty Dang Thien Binh 18/28

And Conquer

1 2 3 4 5 9 10 15

1 2 4 5 3 9 10 15

1 5 2 4 3 10 9 15

5 1 4 2 10 3 9 15

IT Faculty Dang Thien Binh 19/28

Merge Sort

 For MERGE_SORT, an initial array is repeatedly divided

into halves (usually each is a separate array), until
arrays of just one element remain
 At each level of recombination, two sorted arrays are
merged into one
 This is done by copying the smaller of the two elements
from the sorted arrays into the new array, and then
moving along the arrays

1 13 24 26 2 15 27 38

Aptr Bptr Cptr

IT Faculty Dang Thien Binh 20/28

Merging

1 13 24 26 2 15 27 38 1

Aptr Bptr Cptr

1 13 24 26 2 15 27 38 1 2

Aptr Bptr Cptr

1 13 24 26 2 15 27 38 1 2 13

Aptr Bptr Cptr

etc.

IT Faculty Dang Thien Binh 21/28

Merge Sort Algorithm

 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)

IT Faculty Dang Thien Binh 22/28

Merge Sort Algorithm

IT Faculty Dang Thien Binh 23/28

Merge Sort Algorithm

 Video Content
 An illustration of Merge Sort with Transylvanian-saxon (German)
folk dance.

IT Faculty Dang Thien Binh 24/28

Merge Sort Algorithm

IT Faculty Dang Thien Binh 25/28

Merge Sort Algorithm

 Note:
 The MERGE_SORT(A, p, r) sorts the elements in the subarray
A[p .. r]
 If p >= r, the subarray has at most one element and is therefore
already sorted
 The procedure MERGE(A, p, q, r), where p <= q < r, merges two
already sorted subarrays A[p ..q] and A[q+1 .. r]. It takes (n)
time
 To sort an array A[1 .. n], we call MERGE_SORT(A, 1, n)

IT Faculty Dang Thien Binh 26/28

Analyzing Divide-And-Conquer Algorithms

 Running time is described by a recurrence equation or

recurrence
 Assume:
 A problem is divided into a subproblems, each of which is 1/b
the size of the original
 Dividing the problem takes D(n) time
 Combining the solutions to subproblems into the solution to
the original problem takes C(n) time
 T(n) = (1) if n <= c,
= aT(n/b) + D(n) + C(n) otherwise.

IT Faculty Dang Thien Binh 27/28

Analyzing Divide-And-Conquer Algorithms

 Analysis of Merge Sort

 Divide: Computes the middle of the subarray D(n) = (1)
 Conquer: We recursively solve two subproblems, each of size
n/2, contributing 2T(n/2)
 Combine: The MERGE procedure takes (n),
so, C(n) = (n)
 The worst-case running time of merge sort is:
 T(n) = (1) if n = 1,
= 2T(n/2) + (n) if n > 1

IT Faculty Dang Thien Binh 28/28

 Thanks to contributors
Mr. Pham Van Nguyen (2022)
Dr. Thien-Binh Dang (2017 – 2022)
Prof. Hyunseung Choo (2001 – 2022)

IT Faculty Copyright
Dang2000-2022
Thien BinhIT Faculty
29/28