Lesson 04 – OOP and Algorithm Basics

Prerequisites: Review Lesson 02 – Python Basics and Lesson 03 – SQL Foundations to ensure you're comfortable with fundamental syntax and data handling.

This lesson introduces object-oriented programming (OOP) in Python and walks through several classic algorithms. You will learn how classes encapsulate data, how inheritance creates specialized types, and how to implement common sorting and searching routines.

---

1. Why Object-Oriented Programming?

OOP organizes code around objects—bundles of data and behavior. Each object is an instance of a class, which defines the attributes and methods the object supports. This model helps manage complexity by grouping related logic together.

Advantages of OOP include:

• Reusability through inheritance and composition
• Clear organization of data and behavior
• The ability to model real-world concepts directly

---

2. Building Classes and Objects

A class acts as a blueprint for creating objects. Below is a simple Student class with a few core features.

class Student:
    """Represent a student and the grades earned."""

    def __init__(self, name: str) -> None:
        self.name = name
        self.grades: list[int] = []
        """Grades earned by the student across assignments."""

    def add_grade(self, score: int) -> None:
        """Record a new grade for the student."""
        self.grades.append(score)

    def average(self) -> float:
        """Calculate the student's average grade."""
        return sum(self.grades) / len(self.grades)

Create an object by calling the class as if it were a function:

alice = Student("Alice")
alice.add_grade(95)
print(alice.average())  # 95.0

---

3. Inheritance and Polymorphism

A subclass inherits attributes and methods from its parent class. It can override or extend behavior to create more specialized objects.

class Dog:
    """Simple dog that can bark."""

    def bark(self) -> str:
        """Return a bark sound."""
        return "woof"

class ServiceDog(Dog):
    """Dog trained to assist its owner."""

    def assist(self) -> str:
        """Perform a helpful action."""
        return "guiding"

classDiagram
    class Dog {
        +bark()
    }
    class ServiceDog {
        +assist()
    }
    Dog <|-- ServiceDog

ServiceDog automatically gets the bark() method from Dog but also defines its own assist() behavior.

---

4. Essential Algorithms

Algorithms are step‑by‑step instructions to solve a problem. Here are common examples you should know.

Bubble Sort

Bubble Sort repeatedly steps through the list, swapping adjacent items that are out of order.

def bubble_sort(nums: list[int]) -> None:
    """Sort a list of numbers in place using Bubble Sort."""
    n = len(nums)
    for i in range(n):
        for j in range(0, n - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]

Insertion Sort

Insertion Sort builds the sorted list one element at a time by inserting items into their correct position.

def insertion_sort(nums: list[int]) -> None:
    """Sort numbers in place using Insertion Sort."""
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > key:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = key

Merge Sort

Merge Sort uses a divide‑and‑conquer strategy. It splits the list into halves, recursively sorts them, and then merges the sorted halves back together.

def merge_sort(nums: list[int]) -> list[int]:
    """Return a new sorted list using Merge Sort."""
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)


def merge(left: list[int], right: list[int]) -> list[int]:
    """Merge two pre-sorted lists into one sorted list."""
    result: list[int] = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Linear Search

Check each item one by one until you find the target.

def linear_search(items: list[int], target: int) -> int:
    """Return the index of target or -1 if not found."""
    for idx, value in enumerate(items):
        if value == target:
            return idx
    return -1

Binary Search

Binary Search works on sorted data. It repeatedly divides the search space in half.

def binary_search(items: list[int], target: int) -> int:
    """Return the index of target or -1 if not found."""
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

---

5. Complexity and Big O Notation

Algorithm efficiency is often described using Big O notation. It approximates how runtime grows as input size increases.

Algorithm	Big O (Average)
Bubble Sort	O(n^2)
Insertion Sort	O(n^2)
Merge Sort	O(n log n)
Linear Search	O(n)
Binary Search	O(log n)

Understanding complexity helps you choose the best approach for a given problem.

---

6. Try It Yourself

• Implement a Dog class with at least one additional method.
• Add grades to a Student object and print the average.
• Write functions for Bubble Sort and Binary Search and test them on sample lists.
• Describe in your own words why Merge Sort is more efficient than Bubble Sort for large datasets.

---

Would you like this lesson exported to a PDF or used as-is for your coursework?

Next Up

Head to Lesson 05 – SOLID Design Principles to learn how to structure code that remains flexible and maintainable.