Design and Analysis of
Algorithms
Notes by: Sharma Thankachan
Instructor: Charles Hughes
Week 1.2: Getting Started
(Simple Sorts)
Slides modified from Dr. Hon, with permission 1
About this lecture
• Study a few simple algorithms for sorting
– Insertion Sort
– Selection Sort
– Merge Sort
• Show why these algorithms are correct
• Try to analyze the efficiency of these
algorithms (how fast they run)
2
The Sorting Problem
Input: A list of n numbers
Output: Arrange the numbers in
increasing order
Remark: Sorting has many applications.
E.g., if the list is already sorted, we can search a
number in the list faster
3
Insertion Sort
• Operates in n rounds
Swap towards left side ;
• At the kth round, Stop until seeing an item
with a smaller value.
……
kth item
Question: Why is this algorithm correct?
4
Selection Sort
• Operates in n rounds
• At the kth round,
– Find minimum item after (k-1)th position
– Let’s call this minimum item X
– Insert X at kth position in the list by
swapping it with what is there
Question: Why is this algorithm correct?
5
Selection Sort Timing
• Best case is worst case as always
search remaining list for smallest
• All cases are
• Takes n-1 + n-2 + n-3 + … + 1
• Again, the known sum = n (n-1) / 2
• Thus, all cases have an n2 dominant term
6
Divide and Conquer
• Divide a big problem into smaller problems
è solve smaller problems separately
è combine the results to solve original one
• This idea is called Divide-and-Conquer
• Smart idea to solve complex problems (why?)
• Can we apply this idea for sorting ?
7
Divide-and-Conquer for Sorting
• What is a smaller problem ?
è E.g., sorting fewer numbers
è Let’s divide the list to two shorter lists
• Next, solve smaller problems (how?)
• Finally, combine the results
è “merging” two sorted lists into a single
sorted list (how?)
8
Merge Sort
• The previous algorithm, using divide-and-
conquer approach, is called Merge Sort
• The key steps are summarized as follows:
Step 1. Divide list to two halves, A and B
Step 2. Sort A using Merge Sort
Step 3. Sort B using Merge Sort
Step 4. Merge sorted lists of A and B
Question: Why is this algorithm correct?
9
Analyzing the Running Times
• Which of previous algorithms is the best?
• Compare their running time on a computer
– But there are many kinds of computers !!!
Standard assumption: Our computer is a RAM
(Random Access Machine), so that
– each arithmetic (such as +, - , x, ÷), memory access,
and control (such as conditional jump, subroutine call,
return) takes constant amount of time
10
Analyzing the Running Times
• Suppose that our algorithms are now
described in terms of RAM operations
è we can count # of each operation used
è we can measure the running time !
• Running time is usually measured as a
function of the input size
– E.g., n in our sorting problem
11
Insertion Sort (Running Time)
The following is a pseudo-code for Insertion Sort.
Each line requires constant RAM operations.
tj = # of times key is compared at round j 11
Insertion Sort (Running Time)
• Let T(n) denote the running time of
insertion sort, on an input of size n
• By combining terms, we have
T(n) = c1n + (c2+c4+c8)(n-1) + c5Σ tj +
(c6+c7) Σ (tj – 1)
• The values of tj are dependent on the
input (not the input size)
13
Insertion Sort (Running Time)
• Best Case:
The input list is sorted, so that all tj = 1
Then, T(n) = c1n + (c2+c4+c5+c8)(n-1)
= Kn + c è linear function of n
• Worst Case:
The input list is sorted in decreasing
order, so that all tj = j-1
Then, T(n) = K1n2 + K2n + K3
è quadratic function of n
14
Why n2 in bad case?
• Again, best case is already sorted
• Completes in n-1 comparisons
• Worst case is inverse sorted
• Takes 1 + 2 + … + n-3 + n-2 + n-1
• That is a known sum = n (n-1) / 2
• Thus, worst case has an n2 dominant term
• Use induction to prove this n2 property
15
Worst-Case Running Time
• In our course (and in most CS research),
we concentrate on worst-case time
• Some reasons for this:
1. Gives an upper bound of running time
2. Worst case occurs fairly often
Remark: Some people also study average-case
running time (they assume input is
drawn randomly)
16
Try this at home
• Revisit pseudo-code for Insertion Sort
– make sure you understand what’s going on
• Write pseudo-code for Selection Sort
• Convince yourself both are correct
17
Merge Sort (Running Time)
The following is a partial pseudo-code for Merge Sort.
The subroutine MERGE(A,p,q,r) is missing.
Can you complete it?
Hint: Create a temp array for merging
18
Merge Sort (Running Time)
• Let T(n) denote the running time of
merge sort, on an input of size n
• Suppose we know that Merge( ) of two
lists of total size n runs in c1n time
• How would you do the merge?
• Then, we can write T(n) as:
T(n) = 2T(n/2) + c1n + c2 when n > 1
T(1) = c3
19
Merge Sort (Running Time)
T(n) = 2T(n/2) + c1n + c2 when n > 1
T(1) = c3
Solving the recurrence, we have
T(n) = 4 T(N/4) + 2 c1n + 2c2
T(n) = 2kT(n/2k) + k c1n + kc2
Let k = lg n
T(n) = 2lg n T(n/2lg n) + k c1n + kc2
T(n) = n T(1) + c1 n lg n + c2 lg n
T(n) = c3 n + c1 n lg n + c2 lg n
T(n) = c1 n lg n + a linear term + a lg term
20
Which Algorithm is Faster?
• Unfortunately, we still cannot tell
– since constants in running times are unknown
• But we do know that if n is VERY large,
worst-case time of Merge Sort must be
smaller than that of Insertion Sort
• Merge Sort is asymptotically faster than
Insertion Sort
21
