Sorting

CENG 303
Design and Analysis
of Algorithms
Notations

• 𝜃(): Bounds a function from above and below, so it defines the exact asymptotic
behavior
• Big O: Defines an upper bound of an algorithm
• Ω(): Defines a lower bound of an algorithm
Big O

• 𝑓 𝑛 = 𝑥 1.5 + 𝑥 1.4
• 𝑓 𝑛 = (20𝑥)7 −𝑥 6 + 5000
• 𝑓 𝑛 = (3𝑥)5 ∗ (2𝑥)3
• 𝑓 𝑛 = log 𝑥 15
• 𝑓 𝑛 = 21500
Calculating Asymptotic Complexity

• 𝑇 𝑛
• How much “work” algorithm needs to do after every iteration
Calculating Asymptotic Complexity

• Example
• Counting: Give the number of items in a linkedlist

v v v … v

𝑛
Calculating Asymptotic Complexity

• Example
• Counting: Give the number of items in a linkedlist Work
• Count and mark the
first item that has no
v v v … v mark
• Move the next
unmarked item
𝑛
Calculating Asymptotic Complexity

• Example
• Counting: Give the number of items in a linkedlist Work
• Count and mark the
first item that has no
v v v … v mark
• Move the next
unmarked item
𝑛

• 𝑇 𝑛 =𝑇 𝑛−1 +𝑐
Calculating Asymptotic Complexity

• Example
• Counting: Give the number of items in a linkedlist Work
• Count and mark the
first item that has no
v v v … v mark
• Move the next
unmarked item
𝑛

• 𝑇 𝑛 =𝑇 𝑛−1 +𝑐|𝑇 𝑛−1 =𝑇 𝑛−2 +𝑐

• 𝑇 𝑛 =𝑇 𝑛−2 +𝑐+𝑐
Calculating Asymptotic Complexity

• Example
• Counting: Give the number of items in a linkedlist Work
• Count and mark the
first item that has no
v v v … v mark
• Move the next
unmarked item
𝑛
• 𝑇 𝑛 =𝑇 𝑛−1 +𝑐|𝑇 𝑛−1 =𝑇 𝑛−2 +𝑐
• 𝑇 𝑛 =𝑇 𝑛−2 +𝑐+𝑐
• 𝑇 𝑛 = 𝑛𝑐
Calculating Asymptotic Complexity

• Example
• Finding the biggest number in an array

2 3 6 2 1 2 6 3
Calculating Asymptotic Complexity

• Example
• Finding the biggest number in an array Work
• Mark the first item that
2 3 6 2 1 2 6 3 has no mark
• If it is biggest so far,
make it the biggest
• Else, move the next
unmark item
Calculating Asymptotic Complexity

• Example
• Finding the biggest number in an array Work
• Mark the first item that
2 3 6 2 1 2 6 3 has no mark
• If it is biggest so far,
make it the biggest
• Else, move the next
• 𝑇 𝑛 =𝑇 𝑛−1 +𝑐 unmark item
• 𝑇 𝑛 = 𝑛𝑐
Calculating Asymptotic Complexity

• Example
• Finding an item in a Binary Tree
Calculating Asymptotic Complexity

• Example
• Finding an item in a Binary Tree Work
• Mark the root
• If the item is smaller
than the root, search
the left subtree
• Else if the item is
bigger than the root,
search the right
subtree
• 𝑇 𝑛 = 𝑇 𝑛/2 + 𝑐 • Else return the root.
Calculating Asymptotic Complexity

• Example
• Finding an item in a Binary Tree Work
• Mark the root
• If the item is smaller
than the root, search
the left subtree
• Else if the item is
bigger than the root,
search the right
subtree
• 𝑇 𝑛 = 𝑇 𝑛/2 + 𝑐 | 𝑇 𝑛/2 = 𝑇 𝑛/4 + 𝑐 • Else return the root.
• 𝑇 𝑛 = 𝑇 𝑛/4 + 𝑐 + 𝑐
Calculating Asymptotic Complexity

• Example
• Finding an item in a Binary Tree Work
• Mark the root
• If the item is smaller
than the root, search
the left subtree
• Else if the item is
bigger than the root,
search the right
• 𝑇 𝑛 = 𝑇 𝑛/2 + 𝑐 | 𝑇 𝑛/2 = 𝑇 𝑛/4 + 𝑐 subtree
• 𝑇 𝑛 = 𝑇 𝑛/4 + 𝑐 + 𝑐 • Else return the root.
• 𝑇 𝑛 = c ∗ log 𝑛
Calculating Asymptotic Complexity

• Example
• Sorting a given array using bubble sort

2 3 6 2 1 2 6 3
Calculating Asymptotic Complexity

• Example
• Sorting a given array using bubble sort Work
• Compare the first two
2 3 6 2 1 2 6 3 unmarked elements
• If the first one is bigger
• 𝑇 𝑛 =𝑇 𝑛−1 +𝑛 than the second one,
swap, and mark it
• Else mark the first one
• Move the next two
elements until hitting
the last element
• Mark the last element
as the biggest
Calculating Asymptotic Complexity

• Example
• Sorting a given array using bubble sort Work
• Compare the first two
2 3 6 2 1 2 6 3 unmarked elements
• If the first one is bigger
• 𝑇 𝑛 = 𝑇 𝑛 − 1 + 𝑛𝑐| 𝑇 𝑛 − 1 = 𝑇 𝑛 − 2 + 𝑛 − 1 𝑐 than the second one,
swap, and mark it
• 𝑇 𝑛 = 𝑇 𝑛 − 2 + 𝑛𝑐 + 𝑛 − 1 𝑐 • Else mark the first one
• Move the next two
elements until hitting
the last element
• Mark the last element
as the biggest
Calculating Asymptotic Complexity

• Example
• Sorting a given array using bubble sort Work
• Compare the first two
2 3 6 2 1 2 6 3 unmarked elements
• If the first one is bigger
• 𝑇 𝑛 = 𝑇 𝑛 − 1 + 𝑛𝑐| 𝑇 𝑛 − 1 = 𝑇 𝑛 − 2 + 𝑛 − 1 𝑐 than the second one,
swap, and mark it
• 𝑇 𝑛 = 𝑇 𝑛 − 2 + 𝑛𝑐 + 𝑛 − 1 𝑐 • Else mark the first one
• 𝑇 𝑛 = 𝑐 ∗ 𝑛 ∗ (𝑛 − 1)/2 • Move the next two
elements until hitting
the last element
• Mark the last element
as the biggest
Sorting

• Input: A sequence of 𝑛 numbers 𝑎1 , 𝑎2 , … , 𝑎𝑛

• Output: A permutation (reordering) 𝑎′1 , 𝑎′2 , … , 𝑎′𝑛
• For example
• Given the input sequence 2,4,1,3,5,7,2,1,9,8,10
• Returns 1,1,2,2,3,4,5,7,8,9,10
Sorting

• Dictionary
• Binary Search
• Maximum and Minimum Element
• Inserting an Element
• Deleting an Element
Insertion Sort

• A sequence of 𝑛 numbers A = ‫𝑎ۦ‬1 , 𝑎2 , … , 𝑎𝑛 ۧ

• Start with 𝑎2
• Compare 𝑎2 with the 𝑎1
• All the elements on the left-hand side
• Place 𝑎2 accordingly
• Do the same for all elements
Insertion Sort
Insertion Sort
Analysis of Insertion Sort

• The time taken by Insertion Sort

• Number of items
• How nearly sorted the elements already are
• Input Size
• Number of items
• Total number of bits
• The number of vertices and edges
• Running Time
Analysis of Insertion Sort
Analysis of Insertion Sort
Analysis of Insertion Sort

𝑎𝑛2 + 𝑏𝑛 + 𝑐
Merge Sort

• A great example for divide and conquer

• Divide
• Subproblems
• Smaller instances, but the same problem
• Conquer
• Solve recursively
• If subproblems are small enough, straightforward
Merge Sort

• 𝐴 = 5, 2, 4, 7, 1, 3, 2, 6
Merge Sort

• 𝐴 = 5, 2, 4, 7, 1, 3, 2, 6
Merge Sort
Merge Sort
Complexity of Merge Sort

• Divide
• Calculating midpoints of subarrays: 𝑂(𝑛)
• Conquer
• 2 𝑇(𝑛/2)
• Merge
• Line 1-3 and 8-11 are constant time
• Line 4-7 take 𝑂 𝑛1 + 𝑛2 which is 𝑂(𝑛)
• Line 12-17 take constant time and are executed log 𝑛 times: 𝑂(𝑛)