LECTURE 2 SORTING
Beakal Gizachew
Based on slides of Serdar Taşıran, Shafi Goldwasser, Erik Demaine, and Alptekin Küpçü
SORTING
• Sorting
• Input: a sequence of n numbers <a1,a2,…,an>
• Output: a re-ordering <a’1,a’2,…,a’n> of the sequence such that a’1 a’2
… a’n
• Example:
• Input 8 2 4 9 3 6
• Output 2 3 4 6 8 9
• Called an instance of the problem
• Check these demos:
• http://www.iti.fh-
flensburg.de/lang/algorithmen/sortieren/sortcontest/sortcontest.htm
• http://www.cs.oswego.edu/~mohammad/classes/csc241/samples/sort/Sor
t2-E.html
• http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html
• http://www.cs.pitt.edu/~kirk/cs1501/animations/Sort3.html
2
INSERTION SORT
• Takes array A[1..n] containing a sequence of length n to be sorted
• Sorts the array in place
• Numbers re-arranged inside A with at most a constant number of
them stored outside.
• O(1) extra space
3
4
Insertion Sort
To insert 12, we need to make
room for it by moving first 36
and then 24.
5
Insertion Sort
6
Insertion Sort
7
Insertion Sort
INSERTION SORT
INSERTION-SORT (A, n) ⊳ A[1 . . n]
for j ← 2 to n
do key ← A[ j ]
i←j–1
“pseudocode”
while i > 0 and A[ i ] > key
do A[i+1] ← A[ i]
i←i–1
A[i+1] = key
1 i j n
A:
key
sorted
8
EXAMPLE OF INSERTION SORT
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
2 3 4 8 9 6
2 3 4 6 8 9 done
9
EXAMPLE OF INSERTION SORT
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
2 3 4 8 9 6
2 3 4 6 8 9 done
10
CORRECTNESS OF INSERTION
SORT
INSERTION-SORT (A, n) ⊳ A[1 . . n]
for j ← 2 to n
do key ← A[ j ]
i←j–1
while i > 0 and A[ i ] > key
do A[i+1] ← A[ i]
i←i–1
A[i+1] = key
• Loop invariant:
• At the start of each iteration, the subarray A[1..j-1] containsthe
elements originally in A[1..j-1] but in sorted (increasing) order
• Prove initialization, maintenance, termination
• Invariant must imply interesting property about algorithm
11
RUNNING TIME
• The running time of insertion sort depends on the input: e.g., an
already sorted sequence is easier to sort.
• Major Simplifying Convention: Parameterize the running time by
the size of the input, since short sequences are easier to sort than
long ones.
➢ TA(n) = time of A when run with inputs of length n
➢ n: Number of bits required to encode input
➢ Ignore machine-dependent constants
➢ Look at growth of T(n) as n → ∞
➢ For small inputs, the algorithm will run fast anyway. Important
thing is for how big inputs we can still run the algorithm given a
reasonable amount of time.
12
KINDS OF ANALYSES
• Worst-case: (mostly-used)
• T(n) = maximum time of algorithm on any input of size n.
• Generally, we seek upper bounds on the running time, to have a
guarantee of performance.
• Average-case: (sometimes used)
• T(n) = expected time of algorithm over all inputs of size n.
• Need assumption of statistical distribution of real inputs.
• Best-case: (almost never used)
• T(n) = best possible time of algorithm over any input of size n.
• Cheat with a slow algorithm that works fast on some input.
• May be useful when proving negative results
• e.g., Even the best case of algorithm X is slower than the worst
case of algorithm Y.
13
Analysis of Insertion Sort
INSERTION-SORT(A) cost times
for j ← 2 to n c1 n
do key ← A[ j ] c2 n-1
Insert A[ j ] into the sorted sequence A[1 . . j -1] 0 n-1
i←j-1 c4 n-1
n
while i > 0 and A[i] > key c5 j =2 j
t
c6
n
do A[i + 1] ← A[i] j =2
(t j − 1)
c7
n
i←i–1 j =2
(t j − 1)
A[i + 1] ← key c8 n-1
tj: # of times the while statement is executed at iteration j
T (n) = c1n + c2 (n − 1) + c4 (n − 1) + c5 t j + c6 (t j − 1) + c7 (t j − 1) + c8 (n − 1)
n n n
j =2 j =2 j =2
14
INSERTION SORT ANALYSIS
Worst case: Input reverse sorted.
T(n) = σ 𝒏 Θ(𝒋) = Θ(n2) [arithmetic series]
𝒋=𝟐
Average case: All permutations equally likely.
T(n) = σ 𝒏 Θ(𝒋ൗ 𝟐) = Θ(n2)
𝒋=𝟐
Best case: Input already sorted. O(n)
Is insertion sort a fast sorting algorithm?
• Moderately so, for small n.
• Not at all, for large n.
15
HOW TO DESIGN ALGORITHMS?
• We’ll see many example styles throughout the semester
• Insertion sort was an example of an “incremental algorithm”
• Another common paradigm: Divide and Conquer
• Divide into simpler/smaller sub-problems
• Solve (conquer) sub-problems recursively
• Combine results of sub-problems
16
MERGE SORT
MERGE-SORT A[1 . . n]
If n = 1, return
Recursively sort
A[ 1 . . n/2 ] and A[ n/2+1 . . n ]
Merge the two sorted lists
Key subroutine: MERGE
17
MERGE SORT EXAMPLE
18
MERGING TWO SORTED ARRAYS
20 12
13 11
7 9
2 1
19
MERGING TWO SORTED ARRAYS
20 12
13 11
7 9
2 1
20
MERGING TWO SORTED ARRAYS
20 12 20 12
13 11 13 11
7 9 7 9
2 1 2
21
MERGING TWO SORTED ARRAYS
20 12 20 12
13 11 13 11
7 9 7 9
2 1 2
1 2
22
MERGING TWO SORTED ARRAYS
20 12 20 12 20 12
13 11 13 11 13 11
7 9 7 9 7 9
2 1 2
1 2
23
MERGING TWO SORTED ARRAYS
20 12 20 12 20 12
13 11 13 11 13 11
7 9 7 9 7 9
2 1 2
1 2 7
24
MERGING TWO SORTED ARRAYS
20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11
7 9 7 9 7 9 9
2 1 2
1 2 7
25
MERGING TWO SORTED ARRAYS
20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11
7 9 7 9 7 9 9
2 1 2
1 2 7 9
26
MERGING TWO SORTED ARRAYS
20 12 20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11 13 11
7 9 7 9 7 9 9
2 1 2
1 2 7 9
27
MERGING TWO SORTED ARRAYS
20 12 20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11 13 11
7 9 7 9 7 9 9
2 1 2
1 2 7 9 11
28
MERGING TWO SORTED ARRAYS
20 12 20 12 20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11 13 11 13
7 9 7 9 7 9 9
2 1 2
1 2 7 9 11
29
MERGING TWO SORTED ARRAYS
20 12 20 12 20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11 13 11 13
7 9 7 9 7 9 9
2 1 2
1 2 7 9 11 12
30
MERGING TWO SORTED ARRAYS
20 12 20 12 20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11 13 11 13
7 9 7 9 7 9 9
2 1 2
1 2 7 9 11 12
Time = O(n) to merge a total of n
elements (linear time).
31
ANALYZING MERGE SORT
T(n) MERGE-SORT A[1 . . n]
O(1) If n = 1, return
2T(n/2) Recursively sort
A[ 1 . . n/2 ] and A[ n/2+1 . . n ]
O(n) Merge the two sorted lists
Sloppiness: Should be T( n/2 ) + T( n/2 ) , but it
turns out this does not matter asymptotically.
32
RECURRENCE FOR MERGE SORT
O(1) if n = 1
T(n) =
2T(n/2) + O(n) if n > 1
Note: Usually the base case T(1) = O(1)
33
RECURSION TREE
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
34
RECURSION TREE
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
T(n)
35
RECURSION TREE
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
T(n/2) T(n/2)
36
RECURSION TREE
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn/2 cn/2
T(n/4) T(n/4) T(n/4) T(n/4)
37
RECURSION TREE
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn cn
cn/2 cn/2 cn
h = log n cn/4
cn/4 cn/4 cn/4 cn
…
O(1) #leaves = n O(n)
Total = O(n log n)
38
CONCLUSIONS
• O(n log n) grows more slowly than O(n2).
• Therefore, merge sort asymptotically beats insertion sort in the
worst case.
• In practice, merge sort beats insertion sort for n > 30 or so.
39
MASTER THEOREM
• Let T(n) = a T(n/b) + f(n) where
• a 1, b > 1 are constants
• f(n) is an asymptotically positive function
• Then, T(n) can be bounded asymptotically as follows
• If f(n)=O(𝒏𝐥𝐨𝐠𝒃 𝒂−𝜺) for some > 0, then T(n)=Θ(𝒏𝐥𝐨𝐠𝒃 𝒂 )
• If f(n)=Θ(𝒏𝐥𝐨𝐠𝒃 𝒂 ) then T(n)=Θ(𝒏𝐥𝐨𝐠𝒃 𝒂 log n)
• If f(n)=Ω(𝒏𝐥𝐨𝐠𝒃 𝒂+ɛ) for some > 0, and if, for all sufficiently large n
and a constant c < 1 we have af(n/b) cf(n) , then T(n)=Θ(f(n))
40
