Sorting & Inheritance
Two closing threads. Divide-and-conquer sorting is recursion paying off in speed — $O(n\log n)$ where the obvious approaches give $O(n^2)$. Inheritance finishes the object-oriented thread by letting one piece of code work on several types.
- Implement mergesort and quicksort recursively.
- Explain where the $n\log n$ comes from.
- Write a subclass that extends or overrides a parent.
- Say what polymorphism buys and what it demands.
Sorting is the clearest case where recursion is not just tidier but asymptotically faster. Inheritance is how you avoid writing the same method five times for five related types.
Python's sort is Timsort, a hybrid of mergesort and insertion
sort tuned for partly ordered data. Every GUI framework is a class hierarchy
where a button and a text box are both widgets.
Von Neumann wrote mergesort in 1945, among the first algorithms designed for a stored-program computer. Hoare invented quicksort in 1959 while trying to sort words for a translation project.
Mergesort
def mergesort(xs: list) -> list:
"""Return a new sorted list containing the items of xs.
>>> mergesort([3, 1, 2])
[1, 2, 3]
"""
if len(xs) < 2:
return xs[:]
mid = len(xs) // 2
return _merge(mergesort(xs[:mid]), mergesort(xs[mid:]))
def _merge(left: list, right: list) -> list:
"""Return one sorted list from two sorted lists.
>>> _merge([1, 3], [2, 4])
[1, 2, 3, 4]
"""
out = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i])
i = i + 1
else:
out.append(right[j])
j = j + 1
return out + left[i:] + right[j:]At a million items that is roughly $2 \times 10^7$ operations against $10^{12}$ — the difference between instant and hopeless.
Quicksort
def quicksort(xs: list) -> list:
"""Return a new sorted list containing the items of xs.
>>> quicksort([3, 1, 2])
[1, 2, 3]
"""
if len(xs) < 2:
return xs[:]
pivot = xs[0]
smaller = [x for x in xs[1:] if x < pivot]
larger = [x for x in xs[1:] if x >= pivot]
return quicksort(smaller) + [pivot] + quicksort(larger)Taking the first element as pivot on an already-sorted list puts everything in one partition. The recursion depth becomes $n$ and the cost $O(n^2)$ — the same failure mode as the unbalanced BST in Unit 8, and for the same reason.
Inheritance
A subclass inherits the attributes and methods of its parent, and
may add new ones or replace existing ones. Written
class Child(Parent):.
class Shape:
"""A geometric shape."""
def area(self) -> float:
"""Return the area of this shape.
Subclasses must override this.
"""
raise NotImplementedError
def describe(self) -> str:
"""Return a description of this shape and its area.
>>> Square(3).describe()
'Square with area 9'
"""
return type(self).__name__ + ' with area ' + str(self.area())
class Square(Shape):
"""A square with a given side length."""
def __init__(self, side: float) -> None:
"""Initialize a square with the given side length."""
self.side = side
def area(self) -> float:
"""Return the area of this square."""
return self.side ** 2
class Circle(Shape):
"""A circle with a given radius."""
def __init__(self, radius: float) -> None:
"""Initialize a circle with the given radius."""
self.radius = radius
def area(self) -> float:
"""Return the area of this circle."""
return 3.14159 * self.radius ** 2describe is written once in
Shape and works for every subclass, because it calls
self.area() and Python looks that up on the actual
object.raise NotImplementedError in the parent says
"every subclass must supply this". Instantiating Shape directly
and calling area then fails loudly rather than returning
nonsense.Code written against the parent works on any subclass:
shapes = [Square(2), Circle(1), Square(5)] total = sum(s.area() for s in shapes)
The loop knows nothing about squares or circles. Adding a
Triangle later requires no change to it at all — that is
the entire value of the arrangement.
If Shape.area promises a non-negative number, no subclass may
return a negative one. Code written against the parent relies on that
promise. This is the Liskov substitution principle from Unit 1: a subclass
must be usable anywhere the parent is expected.
class ColouredSquare(Square):
"""A square with a colour."""
def __init__(self, side: float, colour: str) -> None:
"""Initialize a coloured square."""
Square.__init__(self, side) # reuse the parent's setup
self.colour = colourReusing the parent's __init__ rather than repeating it means
a change there propagates automatically. Repeating the assignment would work
today and drift later.
• Forgetting the base case in a recursive sort and recursing
forever.
• Quoting quicksort as $O(n\log n)$ without the average-case
qualifier.
• Overriding a method with one that breaks the parent's
promise.
• Forgetting to call the parent's __init__ from a
subclass.
• Building a deep hierarchy where composition would be simpler. Inherit
only when the subclass genuinely is a kind of the
parent.
Practice
Write out each answer before opening it. Original exercises written for this guide in the style of the course's weekly work.
What is mergesort's base case?
Answer
Why is mergesort $O(n\log n)$?
Answer
What input makes quicksort $O(n^2)$ with a first-element pivot?
Answer
Merge $[1, 4, 6]$ and $[2, 3, 7]$ by hand.
Answer
Data arrives nearly sorted. Which algorithm, and why?
Answer
Add a Rectangle to the Shape
hierarchy.
Solution
class Rectangle(Shape):
"""A rectangle with a width and a height."""
def __init__(self, width: float, height: float) -> None:
"""Initialize a rectangle of the given width and height."""
self.width = width
self.height = height
def area(self) -> float:
"""Return the area of this rectangle."""
return self.width * self.heightdescribe works immediately, with no change to
Shape.Why does describe work for every subclass?
Answer
self.area(), and Python resolves that on the actual object at
run time — so each subclass supplies its own.A Penguin subclasses Bird, which has
fly(). What is wrong?
Answer
fly() on a Bird. The hierarchy is wrong: flying
should belong to a narrower class than Bird. This is the
standard illustration of the Liskov
principle.Expanded topic checklist
Course coverage. This unit is part of the complete CSC148H1 topic map. It should cover the following items before you move on:
- Mergesort. Divide, recurse, merge, and why the cost is $n\log n$.
- Quicksort. Partitioning by value, average case, and the sorted-input worst case.
- Inheritance. Subclasses, overriding, and reusing the parent's initialiser.
- Polymorphism. Writing code against the parent, and the substitution obligation.
The calendar names "object-oriented programming" and "analyzing the efficiency of programs", both of which close here. Check Quercus for the assigned exercises and for whether sorting is examined by code or by analysis.
Recursion applied to sorting buys a better growth rate. Inheritance applied to classes buys reuse. Both are the same instinct as the rest of the course: find the structure in the problem and let the code follow it.
Deep practice extensions
Use these after the main practice set. They push on definitions and edge cases rather than routine calculation.
How do mergesort and quicksort differ structurally?
Guide
Which sort has no bad input?
Guide
What does a subclass owe the parent's contract?
Guide
When is composition better?