01:198:344 Lecture Notes - Lecture 6: Medes, Insertion Sort, Selection Sort
20 Sep 2019
School
Department
Course
Professor
2019-09-19 Design & Analysis of Algorithms
Averages
- Suppose we rate teachers from 1 (worst) to 5 (best)
- And suppose we have 100 teachers:
- 6 teachers are rated 1
- 94 teachers are rated 5
- Average: (6 * 1 + 95 * 5)/100 = 4.76
- So 94% of the teachers are above average
- Averages are also very sensitive to outliers:
- Suppose the test scores on midterm 1 are:
- 35, 36, 37, 38, 39, 40
- Average 37.5
- But on midterm 2 one person did much better
- 35, 36, 37, 38, 39, 100
- Average 47.5
- Medians
- The median of a set of numbers is a value such that half the numbers are greater
than it and half are smaller than it
- For finite, sorted sets with an odd number of elements, we can take the middle
number
- For an even number of elements, we can take the smaller of the two middle
numbers
- For a sorted set, finding the middle element takes constant time
- For unsorted finite sets, we could sort it first and take the middle element
- O(nlogn) + O(1) = O(nlogn)
- Median Sort
- Suppose we have an array where n = 11
- 2, 36, 5, 21, 8, 13, 11, 20, 5, 4, 1
- Pick some v and split the list into 3 lists
- Values less than v (SL)
- Values equal to v (Sv)
- Values greater than v (SR)
- If we pick v = 5 we get
- SL = 2, 4, 1
- Sv = 5, 5
- SR = 36, 21, 8, 13, 11, 20
- Suppose we wanted to find the 8th smallest value
- Recursively search one of the three arrays based on k and the three
sizes
- def selection(S, k)
- if k < len(SL):
- Return selection(SL, k)
- elif k < len(SL) + len(SV):
- Return v
- Else:
- Return selection(SR, k - len(SL) - len(SV))
- Running Time:
- Partitioning S: O(n)
- Recursively search: ?
- If we pick a v that splits the list evenly:
- T(n) = T(n/2) + O(n)
- But that requires v to be the median which is back where
we started
- Idea: pick v randomly
- In the worst case, v is the max/min so we get T(n) = T(n - 1) +
O(n) which is O(n2)
- In the best case, v is the median and we get O(n)
- What is the average time?
- Call v good if it's between the 25th and 75th percentile of S
- Then SL and SR have sizes at most ¾ n
- And there are many such values
- Half the values in S would work
- How many values of v would we have to pick to get a good one?
- Since the probability is ½ the expected number is 2
- We must pick at least one
- If it’s bad, pick again
- So E = 1 + ½ E
- Which gives E = 2
- Expected Running Time: T(n) = T(3n/4) + O(n)
- T(n) = T(3n/4) + Time to shrink S to size ≤
3n/4
- E[T(n)] = E[T(3n/4) + Time to shrink S to
size ≤ 3n/4]
- E[T(3n/4)] + E[Time to shrink S to size ≤
3n/4]
- E[T(n)] = E[T(3n/4)] + E[2 · O(n)]
- E[T(n)] = E[T(3n/4)] + O(n)
- Which is O(n)
- Counting Sort
Document Summary
Suppose we rate teachers from 1 (worst) to 5 (best) Average: (6 * 1 + 95 * 5)/100 = 4. 76. So 94% of the teachers are above average. Averages are also very sensitive to outliers: Suppose the test scores on midterm 1 are: But on midterm 2 one person did much better. The median of a set of numbers is a value such that half the numbers are greater than it and half are smaller than it. For finite, sorted sets with an odd number of elements, we can take the middle number. For an even number of elements, we can take the smaller of the two middle numbers. For a sorted set, finding the middle element takes constant time. For unsorted finite sets, we could sort it first and take the middle element. Suppose we have an array where n = 11. Pick some v and split the list into 3 lists.
