PYTHON PROGRAMMING:Day 17: Basic Algorithms

In Day 16 you learned how to organize data with stacks, queues, and other specialized structures. Now you will learn how to process that data — how to search for a value, sort a list into order, and think about whether your approach scales when the data grows from 10 items to 10 million.

An algorithm is simply a step-by-step recipe for solving a problem. A cake recipe tells you: mix ingredients, bake at 180°C, cool, frost. A sorting algorithm tells you: compare two elements, swap if out of order, repeat until sorted. The idea is the same — a clear sequence of steps that always produces the correct result.

Every app you use relies on algorithms. Google search finds relevant pages among billions. Spotify recommends songs. Your phone's GPS calculates the fastest route. Understanding basic algorithms makes you a stronger programmer — not because you will rewrite Python's built-in sort(), but because you will know why things are fast or slow and how to choose the right approach.

What You Will Learn in This Chapter

By the end of this tutorial you will be able to:

• Explain what an algorithm is and why efficiency matters
• Implement bubble sort and selection sort from scratch
• Implement linear search and binary search
• Understand Big O notation at a beginner level
• Know when to use Python's built-in sorted() and .sort()
• Trace through sorting and searching algorithms step by step
• Avoid common algorithm mistakes (searching unsorted data with binary search, etc.)

Estimated time: 55 minutes reading + 30 minutes practice

What Is an Algorithm?

An algorithm is a finite sequence of well-defined steps that takes an input and produces an output. It must:

1. Terminate — finish in a reasonable amount of time
2. Be correct — always produce the right answer
3. Be unambiguous — each step has exactly one meaning

# This is an algorithm — find the largest number in a list
def find_max(numbers):
    if not numbers:
        return None
    largest = numbers[0]
    for num in numbers[1:]:
        if num > largest:
            largest = num
    return largest

print(find_max([3, 7, 2, 9, 1]))   # 9
print(find_max([42]))               # 42

Output:

9
42

You already write algorithms every time you write a function with logic. The difference now is being intentional about efficiency — how the runtime grows as your input gets bigger.

Algorithm Efficiency — Big O in Plain English

Big O notation describes how an algorithm's runtime (or memory) grows as the input size n increases. You do not need to memorize math formulas — just understand the common categories:

When n is small (dozens of items), even O(n²) algorithms feel instant. When n is large (millions of items), the difference between O(n) and O(n²) is the difference between milliseconds and hours.

Practical rule: In real Python code, use built-in tools (sorted(), in on sets, dict lookups) unless you have a specific reason to write your own. Learn manual implementations to understand how they work, not because you should deploy them in production.

Sorting Algorithms

Sorting arranges data in ascending or descending order. Python's sorted() uses an efficient O(n log n) algorithm called Timsort. But understanding simpler sorts teaches you the core idea: compare adjacent (or selected) elements and swap when they are out of order.

Bubble Sort — Simple but Slow

Bubble sort repeatedly walks through the list, comparing each pair of neighbors and swapping them if they are in the wrong order. Larger values "bubble" toward the end.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

numbers = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(numbers.copy()))

Output:

[11, 12, 22, 25, 34, 64, 90]

Step-by-step on `[64, 34, 25]`:

1. Compare 64 and 34 → swap → [34, 64, 25]
2. Compare 64 and 25 → swap → [34, 25, 64]
3. End of first pass — 64 is in its final position
4. Compare 34 and 25 → swap → [25, 34, 64]
5. Second pass complete — sorted

Time complexity: O(n²) — two nested loops, each running up to n times. Fine for learning; too slow for large datasets.

Selection Sort — Find the Minimum, Swap It Forward

Selection sort finds the smallest element in the unsorted portion and swaps it into the correct position, one element at a time:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

numbers = [64, 34, 25, 12, 22, 11, 90]
print(selection_sort(numbers.copy()))

Output:

[11, 12, 22, 25, 34, 64, 90]

Walkthrough on `[64, 34, 25, 12]`:

1. Scan all four — minimum is 12 at index 3 → swap with index 0 → [12, 34, 25, 64]
2. Scan indices 1–3 — minimum is 25 at index 2 → swap with index 1 → [12, 25, 34, 64]
3. Scan indices 2–3 — minimum is 34 → already in place
4. Done → [12, 25, 34, 64]

Also O(n²), but it makes fewer swaps than bubble sort — useful when writing to memory is expensive.

When to Use Python's Built-in Sort

numbers = [64, 34, 25, 12, 22, 11, 90]

# sorted() — returns a NEW sorted list
sorted_list = sorted(numbers)
print(sorted_list)    # [11, 12, 22, 25, 34, 64, 90]
print(numbers)        # original unchanged

# .sort() — sorts IN PLACE
numbers.sort()
print(numbers)        # [11, 12, 22, 25, 34, 64, 90]

Always prefer sorted() or .sort() in real code. They are fast, well-tested, and handle edge cases you might miss.

Searching Algorithms

Searching finds whether a value exists in a collection and optionally returns its position.

Linear Search — Check Every Item

Linear search walks through the list one item at a time until it finds the target or runs out of items:

def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

numbers = [11, 12, 22, 25, 34, 64, 90]
print(linear_search(numbers, 25))   # 3
print(linear_search(numbers, 99))   # -1 (not found)

Output:

3
-1

Time complexity: O(n) — in the worst case, you check every element. Works on sorted and unsorted data. Python's in operator on a list uses linear search internally.

Binary Search — Halve the Problem Each Step

Binary search is much faster — O(log n) — but it only works on sorted data. The idea: look at the middle element. If the target is smaller, search the left half. If larger, search the right half. Repeat until found or the range is empty.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

sorted_array = [11, 12, 22, 25, 34, 64, 90]
print(binary_search(sorted_array, 25))   # 3
print(binary_search(sorted_array, 99))   # -1

Output:

3
-1

Walkthrough searching for 25 in `[11, 12, 22, 25, 34, 64, 90]`:

1. left=0, right=6, mid=3 → arr[3]=25 → found! Return index 3.

Searching for 34:

1. mid=3 → arr[3]=25 → 34 > 25 → search right half (left=4)
2. mid=5 → arr[5]=64 → 34 < 64 → search left of mid (right=4)
3. mid=4 → arr[4]=34 → found! Return index 4.

Three comparisons instead of five with linear search. On a list of 1 million items, binary search needs at most ~20 comparisons. Linear search might need 1 million.

Putting Sort and Search Together

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

numbers = [64, 34, 25, 12, 22, 11, 90]
print(f"Original: {numbers}")

sorted_nums = bubble_sort(numbers.copy())
print(f"Sorted:   {sorted_nums}")

target = 25
index = binary_search(sorted_nums, target)
print(f"Binary search for {target}: index {index}")

Output:

Original: [64, 34, 25, 12, 22, 11, 90]
Sorted:   [11, 12, 22, 25, 34, 64, 90]
Binary search for 25: index 3

The typical pattern: sort once (O(n log n) with built-in sort), then search many times (O(log n) each with binary search). That beats searching an unsorted list repeatedly with linear search.

Recursion — A Preview

Some algorithms solve problems by breaking them into smaller versions of the same problem — this is recursion. A recursive function calls itself with a smaller input until it hits a base case:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))   # 5 * 4 * 3 * 2 * 1 = 120

Output:

120

Merge sort and quick sort (advanced sorting algorithms) use recursion. You will encounter recursion more in intermediate Python — for now, know that "call yourself with a smaller problem" is a powerful pattern.

Common Mistakes

Mistake 1: Using binary search on unsorted data

# WRONG — binary search requires sorted data
unsorted = [90, 11, 34, 25]
index = binary_search(unsorted, 25)   # unpredictable result

# CORRECT — sort first, then search
sorted_data = sorted(unsorted)
index = binary_search(sorted_data, 25)

Mistake 2: Off-by-one errors in binary search

The loop condition left <= right (not left < right) and updating left = mid + 1 / right = mid - 1 are easy to get wrong. Trace through with a small example whenever your binary search returns incorrect results.

Mistake 3: Reinventing the wheel in production

# Learning exercise — fine
bubble_sort(my_list)

# Production code — use built-ins
my_list.sort()
# or
sorted_list = sorted(my_list)

Mistake 4: Ignoring input size

An O(n²) algorithm on 100 items runs in microseconds. On 100,000 items it can take minutes. Always consider how large your data will grow.

Practice Exercises

Exercise 1: Trace bubble sort by hand on [5, 1, 4, 2, 8]. Write down the list after each complete pass.

Exercise 2: Write a linear search that returns all indices where the target appears, not just the first.

Exercise 3: Given a sorted list of 20 numbers, how many comparisons does binary search need in the worst case? (Hint: keep halving until one element remains.)

Exercise 4: Use Python's sorted() with a key function to sort a list of names by length: ["Alice", "Bob", "Christopher", "Dan"].

→ See all Python practice exercises with solutions

What Comes Next — Day 21: Web Development Basics

Algorithms help you process data efficiently on your machine. The next major step is putting your Python skills on the web — building pages and APIs that anyone with a browser can reach.

Day 21 covers:

• How the web works (HTTP, requests, responses)
• Introduction to Flask — Python's lightweight web framework
• Routes, templates, and JSON responses
• Building your first web application

→ Continue to Day 21: Web Development Basics

Chapter navigation

• Previous: Day 16: Advanced Data Structures
• Next: Day 21: Web Development Basics
• Python Quiz: Take the Python quiz
• All Python exercises: Explore Python exercises