Python course · Module 2: Data Structures

Sorting Algorithms - Species Classification

15 min read ·
In this lesson16

Welcome again! Darwin here with another crucial skill.

Imagine you've discovered 100 different species during an expedition. You need to organize them alphabetically for a catalog. How will you do it? You could:

  • Bubble - compare neighbors, swap them (slow but simple)
  • Select - find the smallest, add to a new list (also slow)
  • Divide and merge - split into halves, sort separately, merge (fast!)

These are sorting algorithms - different ways of ordering data. Each has its own strengths, weaknesses, and complexity!

Why Is Sorting Important?

Sorted data allows for:

  • Faster searching - binary search requires sorted data
  • Easier analysis - easy to find min/max, median
  • Better presentation - alphabetically, chronologically
  • Efficiency - many algorithms work better on sorted data
# Example: Searching in a sorted list
species = ["Elephas", "Gorilla", "Leo", "Loxodonta", "Panthera", "Python"]

# Binary search - O(log n) - but requires sorting!
import bisect
index = bisect.bisect_left(species, "Leo")  # Fast!

# vs unsorted list - O(n)
unsorted_species = ["Python", "Leo", "Gorilla", ...]
index = unsorted_species.index("Leo")  # Slower for large lists

Binary Search - Why a Sorted Catalog Pays Off

A sorted list lets you search more cleverly than entry by entry. Binary search works like looking a species up in a printed field guide: you open it in the middle and immediately know which half to keep searching. Every round repeats the same four steps:

  1. Find the middle element of the range you are searching.
  2. Compare it with the value you are looking for.
  3. If it is not the one, choose the left or the right half - the one where the value can still be.
  4. Repeat on the smaller range until you find the element or the range runs out - then return the result.
def binary_search(sorted_list, target):
    left = 0
    right = len(sorted_list) - 1
    while left <= right:
        mid = (left + right) // 2       # 1. middle of the range
        if sorted_list[mid] == target:  # 2. compare
            return mid                  # 4. found - return the position
        elif sorted_list[mid] < target:
            left = mid + 1              # 3. search the right half
        else:
            right = mid - 1             # 3. search the left half
    return -1                           # 4. not found

species = ["Elephas", "Gorilla", "Leo", "Loxodonta", "Panthera", "Python"]
print(binary_search(species, "Leo"))  # 2

The list has to be sorted - otherwise comparing with the middle tells you nothing about which half holds the species. Every round throws away half of the list, so even a million entries need only about 20 comparisons, which is O(log n).

Python's Built-in Sort

Python has built-in sorting - Timsort (hybrid merge sort + insertion sort).

# 1. list.sort() - sorts in-place (modifies original list)
animals = ["Tiger", "Elephant", "Lion", "Parrot"]
animals.sort()  # Modifies animals
print(animals)  # ['Elephant', 'Lion', 'Parrot', 'Tiger']

# 2. sorted() - returns a new sorted list
animals = ["Tiger", "Elephant", "Lion", "Parrot"]
sorted_animals = sorted(animals)  # New list
print(animals)  # ['Tiger', 'Elephant', 'Lion', 'Parrot'] - unchanged
print(sorted_animals)  # ['Elephant', 'Lion', 'Parrot', 'Tiger']

# 3. Sorting with a key
animals = ["Tiger", "Elephant", "Lion", "Parrot"]
sorted_by_length = sorted(animals, key=len)
print(sorted_by_length)  # ['Lion', 'Tiger', 'Parrot', 'Elephant']

# 4. Reverse sorting
animals.sort(reverse=True)
print(animals)  # ['Tiger', 'Parrot', 'Lion', 'Elephant']

# 5. Sorting dict by values
species_count = {"Python": 5, "Leo": 3, "Elephas": 8}
sorted_species = sorted(species_count.items(), key=lambda x: x[1], reverse=True)
print(sorted_species)  # [('Elephas', 8), ('Python', 5), ('Leo', 3)]

Timsort complexity: O(n log n) worst case, O(n) best case

But understanding classic sorting algorithms will help you:

  • Understand how sorting works "under the hood"
  • Solve interview questions
  • Choose the right algorithm for specific cases

Bubble Sort

Idea: Compare adjacent elements and swap them if they are in the wrong order. Repeat until everything is sorted.

Safari analogy: Like air bubbles in water - in every pass the largest unsorted element "floats" to the end of the list, like a bubble rising to the surface.

def bubble_sort(arr):
    """
    Bubble sort - O(n²)

    Algorithm:
    1. Go through the entire list
    2. Compare each pair of adjacent elements
    3. Swap them if they are in the wrong order
    4. Repeat until nothing changes
    """
    n = len(arr)

    for i in range(n):
        # After each iteration the largest element "floats" to the end
        swapped = False  # Optimization - if nothing changed, list is sorted

        for j in range(0, n - i - 1):  # Skip last i elements (already sorted)
            if arr[j] > arr[j + 1]:
                # Swap
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        if not swapped:
            break  # List already sorted

    return arr

# Example
species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
sorted_species = bubble_sort(species.copy())
print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']

# Step by step:
# Pass 1: ["Leo", "Elephas", "Gorilla", "Panthera", "Python"]  # Python "floated" up
# Pass 2: ["Elephas", "Gorilla", "Leo", "Panthera", "Python"]  # Panthera "floated" up
# Pass 3: ["Elephas", "Gorilla", "Leo", "Panthera", "Python"]  # Already sorted

Complexity:

  • Time: O(n²) worst and average, O(n) best (for already sorted list)
  • Memory: O(1) - sorts in-place
  • Stable: Yes - preserves order of equal elements

Pros: Simple, stable, good for small data or nearly sorted Cons: Very slow for large data - O(n²)

Selection Sort

Idea: Find the smallest element and place it at the beginning. Find the second smallest and place it at the second position. Repeat.

Safari analogy: Picking the smallest species one by one for a sorted catalog.

def selection_sort(arr):
    """
    Selection sort - O(n²)

    Algorithm:
    1. Find the smallest element in the unsorted part
    2. Swap it with the first element of the unsorted part
    3. Move the sorted boundary by 1
    4. Repeat
    """
    n = len(arr)

    for i in range(n):
        # Find index of smallest element in unsorted part
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        # Swap smallest element with first unsorted
        arr[i], arr[min_index] = arr[min_index], arr[i]

    return arr

# Example
species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
sorted_species = selection_sort(species.copy())
print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']

# Step by step:
# i=0: ["Elephas", "Leo", "Python", "Gorilla", "Panthera"]  # Found min: Elephas
# i=1: ["Elephas", "Gorilla", "Python", "Leo", "Panthera"]  # Found min: Gorilla
# i=2: ["Elephas", "Gorilla", "Leo", "Python", "Panthera"]  # Found min: Leo
# i=3: ["Elephas", "Gorilla", "Leo", "Panthera", "Python"]  # Found min: Panthera
# i=4: Done

Complexity:

  • Time: O(n²) always - even for sorted list!
  • Memory: O(1) - sorts in-place
  • Stable: No - may change order of equal elements

Pros: Simple, predictable time, few swaps Cons: Slow - always O(n²), unstable

Insertion Sort

Idea: Build a sorted list element by element, inserting each new element at the right position.

Safari analogy: Like arranging cards in your hand - you take a card and insert it in the right place.

def insertion_sort(arr):
    """
    Insertion sort - O(n²)

    Algorithm:
    1. Start from the second element
    2. Compare it with elements to the left
    3. Shift larger elements to the right
    4. Insert element at the right position
    5. Repeat for each element
    """
    for i in range(1, len(arr)):
        key = arr[i]  # Element to insert
        j = i - 1

        # Shift elements greater than key one position to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        # Insert key at the right position
        arr[j + 1] = key

    return arr

# Example
species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
sorted_species = insertion_sort(species.copy())
print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']

# Step by step:
# i=1 (Leo):      ["Leo", "Python", "Elephas", "Gorilla", "Panthera"]
# i=2 (Elephas):  ["Elephas", "Leo", "Python", "Gorilla", "Panthera"]
# i=3 (Gorilla):  ["Elephas", "Gorilla", "Leo", "Python", "Panthera"]
# i=4 (Panthera): ["Elephas", "Gorilla", "Leo", "Panthera", "Python"]

Complexity:

  • Time: O(n²) worst and average, O(n) best (for nearly sorted)
  • Memory: O(1) - sorts in-place
  • Stable: Yes

Pros: Simple, stable, great for small or nearly sorted data, online (can sort while receiving data) Cons: Slow for large unordered data - O(n²)

Timsort uses insertion sort for small sublists (<64 elements)!

Merge Sort

Idea: Divide the list into halves, sort recursively, merge sorted halves.

Safari analogy: Divide the team into smaller groups, each group sorts separately, then you combine results.

def merge_sort(arr):
    """
    Merge sort - O(n log n)

    Algorithm (Divide and Conquer):
    1. If list has 1 element - already sorted
    2. Divide list into two halves
    3. Sort each half recursively
    4. Merge two sorted halves
    """
    if len(arr) <= 1:
        return arr

    # Divide
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # Merge
    return merge(left, right)

def merge(left, right):
    """
    Merge two sorted lists into one sorted list
    """
    result = []
    i = j = 0

    # Compare elements from both lists and add the smaller one
    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

    # Add remaining elements (one list is empty)
    result.extend(left[i:])
    result.extend(right[j:])

    return result

# Example
species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
sorted_species = merge_sort(species)
print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']

# Recursion tree:
# ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
#       /                                  \
# ["Python", "Leo"]                  ["Elephas", "Gorilla", "Panthera"]
#   /        \                           /                \
# ["Python"] ["Leo"]               ["Elephas"]    ["Gorilla", "Panthera"]
#                                                      /            \
#                                                ["Gorilla"]    ["Panthera"]
# Merging:
# ["Leo", "Python"]                 ["Elephas", "Gorilla", "Panthera"]
#                \                    /
#         ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']

Complexity:

  • Time: O(n log n) always - worst, average, best
  • Memory: O(n) - creates new lists during merging
  • Stable: Yes

Pros: Predictable O(n log n), stable, good for large data Cons: Uses additional O(n) memory

Quick Sort

Idea: Choose a pivot, divide the list into elements smaller and larger than pivot, sort each part recursively.

Safari analogy: Pick a "median" species, divide into smaller and larger, repeat.

def quick_sort(arr):
    """
    Quick sort - O(n log n) average, O(n²) worst

    Algorithm:
    1. If list has ≤1 element - already sorted
    2. Choose pivot (e.g., last element)
    3. Divide into: smaller than pivot, equal to pivot, larger than pivot
    4. Recursively sort smaller and larger
    5. Combine: [sorted smaller] + [pivot] + [sorted larger]
    """
    if len(arr) <= 1:
        return arr

    # Choose pivot (e.g., last element)
    pivot = arr[-1]

    # Divide into 3 groups
    smaller = [x for x in arr[:-1] if x < pivot]
    equal = [x for x in arr if x == pivot]
    larger = [x for x in arr[:-1] if x > pivot]

    # Recursively sort and combine
    return quick_sort(smaller) + equal + quick_sort(larger)

# More efficient version (in-place):
def quick_sort_inplace(arr, low=0, high=None):
    """Quick sort in-place with Lomuto partitioning"""
    if high is None:
        high = len(arr) - 1

    if low < high:
        # Partition and get pivot index
        pivot_index = partition(arr, low, high)

        # Sort parts before and after pivot
        quick_sort_inplace(arr, low, pivot_index - 1)
        quick_sort_inplace(arr, pivot_index + 1, high)

    return arr

def partition(arr, low, high):
    """Lomuto partitioning"""
    pivot = arr[high]  # Choose last element as pivot
    i = low - 1  # Index of smaller element

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    # Place pivot at the right position
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# Example
species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
sorted_species = quick_sort(species)
print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']

Complexity:

  • Time: O(n log n) average, O(n²) worst (when pivot is always the worst choice)
  • Memory: O(log n) recursion (in-place version)
  • Stable: No (standard implementation)

Pros: Very fast in practice, sorts in-place (low memory) Cons: Unstable, O(n²) worst case, requires good pivot selection

Sorting Algorithm Comparison

AlgorithmBestAverageWorstMemoryStable
Bubble SortO(n)O(n²)O(n²)O(1)Yes
Selection SortO(n²)O(n²)O(n²)O(1)No
Insertion SortO(n)O(n²)O(n²)O(1)Yes
Merge SortO(n log n)O(n log n)O(n log n)O(n)Yes
Quick SortO(n log n)O(n log n)O(n²)O(log n)No
Python sort()O(n)O(n log n)O(n log n)O(n)Yes

When to Use Which Algorithm?

# Small data (<50 elements) or nearly sorted
# → Insertion Sort
small_list = ["Python", "Leo", "Elephas"]
insertion_sort(small_list)  # Fast for small data!

# Large data, need stability
# → Merge Sort or Python sort()
import random

large_list = [random.random() for _ in range(10000)]
sorted_list = sorted(large_list)  # Timsort - stable!

# Large data, limited memory, don't need stability
# → Quick Sort (in-place)
import random

large_list = [random.random() for _ in range(10000)]
quick_sort_inplace(large_list)  # Low memory!

# In practice: ALWAYS use Python sort() or sorted()
# They are optimized, stable, and very fast (Timsort)!
animals.sort()  # Best choice in 99% of cases!

Sorting Species by Different Criteria

You can build a sort key from any information about a species. Below, the same list of dictionaries is sorted in three ways; lambda s: s["name"] is a short function that gives the value to compare for each species (we will look at it more closely in the project at the end of the module):

species_list = [
    {"name": "Python regius", "size": 1.5, "dangerous": False},
    {"name": "Panthera leo", "size": 2.5, "dangerous": True},
    {"name": "Elephas maximus", "size": 3.5, "dangerous": False},
    {"name": "Crocodylus niloticus", "size": 4.5, "dangerous": True},
    {"name": "Gorilla gorilla", "size": 1.8, "dangerous": False}
]

# 1. Sort by name
sorted_by_name = sorted(species_list, key=lambda s: s["name"])
for s in sorted_by_name:
    print(s["name"])
# Crocodylus niloticus, Elephas maximus, Gorilla gorilla, Panthera leo, Python regius

# 2. Sort by size (descending)
sorted_by_size = sorted(species_list, key=lambda s: s["size"], reverse=True)
for s in sorted_by_size:
    print(f"{s['name']}: {s['size']}m")
# Crocodylus niloticus: 4.5m, Elephas maximus: 3.5m, Panthera leo: 2.5m, ...

# 3. Dangerous first, then from the largest
sorted_by_danger_size = sorted(species_list, key=lambda s: (not s["dangerous"], -s["size"]))
for s in sorted_by_danger_size:
    danger = "dangerous" if s["dangerous"] else "safe"
    print(f"{s['name']}: {s['size']}m ({danger})")
# Crocodylus niloticus: 4.5m (dangerous)
# Panthera leo: 2.5m (dangerous)
# Elephas maximus: 3.5m (safe)
# ...

Counting Sort - For Special Cases

If we're sorting integers from a limited range, we can use Counting Sort - O(n + k)!

def counting_sort(arr, max_value):
    """
    Counting sort - O(n + k) where k = max_value

    Works only for integers in range [0, max_value]
    """
    # Count occurrences of each number
    count = [0] * (max_value + 1)
    for num in arr:
        count[num] += 1

    # Build sorted list
    sorted_arr = []
    for num, freq in enumerate(count):
        sorted_arr.extend([num] * freq)

    return sorted_arr

# Safari example: Sorting number of discoveries (0-100)
daily_discoveries = [5, 3, 8, 3, 12, 5, 7, 3, 10, 5]
sorted_discoveries = counting_sort(daily_discoveries, max(daily_discoveries))
print(sorted_discoveries)  # [3, 3, 3, 5, 5, 5, 7, 8, 10, 12]

# O(n) for limited range! Faster than O(n log n) for large n!

Practical Example - Cataloging System

The example below wraps the list and its functions in a class - you will meet classes in module 3, so for now read it as a set of functions working on one list:

class SpeciesCatalog:
    """Species cataloging system with various sorts"""

    def __init__(self):
        self.species = []

    def add_species(self, name, size, habitat, dangerous):
        """Add species to catalog"""
        self.species.append({
            "name": name,
            "size": size,
            "habitat": habitat,
            "dangerous": dangerous
        })

    def sort_by_name(self):
        """Sort alphabetically"""
        return sorted(self.species, key=lambda s: s["name"])

    def sort_by_size(self, descending=True):
        """Sort by size"""
        return sorted(self.species, key=lambda s: s["size"], reverse=descending)

    def sort_by_danger_then_size(self):
        """Sort: dangerous first, then by size"""
        return sorted(self.species, key=lambda s: (not s["dangerous"], -s["size"]))

    def filter_and_sort(self, habitat=None, min_size=None, sort_by="name"):
        """Filter and sort"""
        filtered = self.species

        if habitat:
            filtered = [s for s in filtered if s["habitat"] == habitat]

        if min_size:
            filtered = [s for s in filtered if s["size"] >= min_size]

        if sort_by == "name":
            return sorted(filtered, key=lambda s: s["name"])
        elif sort_by == "size":
            return sorted(filtered, key=lambda s: s["size"], reverse=True)

        return filtered

# Usage
catalog = SpeciesCatalog()
catalog.add_species("Python regius", 1.5, "jungle", False)
catalog.add_species("Panthera leo", 2.5, "savanna", True)
catalog.add_species("Elephas maximus", 3.5, "jungle", False)
catalog.add_species("Crocodylus niloticus", 4.5, "river", True)

# Large jungle species sorted by size
jungle_large = catalog.filter_and_sort(habitat="jungle", min_size=2.0, sort_by="size")
for s in jungle_large:
    print(f"{s['name']}: {s['size']}m")
# Elephas maximus: 3.5m

Practical Exercise

The editor holds distances to a watering hole and a list of snakes:

  1. Sort the list distances in ascending order with sort() and print it
  2. Use sorted() with reverse=True to build a new descending list from species without changing the original
Code for this lesson: main.py
# Sorting lists
# .sort() modifies the original list, sorted() creates a new one

animal_weights = [450, 120, 5000, 30, 900, 1500]
animal_names = ["cheetah", "lion", "elephant", "zebra", "antelope", "buffalo"]

# sort() - sorts in place (modifies the original list)
animal_weights.sort()
print(f"Weights ascending: {animal_weights}")

animal_weights.sort(reverse=True)
print(f"Weights descending: {animal_weights}")

# sorted() - returns a NEW sorted list
sorted_names = sorted(animal_names)
print(f"\nNames alphabetically: {sorted_names}")
print(f"Original list: {animal_names}")  # Unchanged!

# TODO: Create a list of distances to a watering hole (in km)
distances = [12.5, 3.2, 8.7, 1.1, 15.3, 6.4]

# TODO: Sort distances in ascending order using .sort()


# TODO: Display the sorted list
print(f"Distances ascending: {distances}")

# TODO: Use sorted() with reverse=True to get descending order WITHOUT changing the original list
species = ["python", "cobra", "mamba", "anaconda", "boa"]
sorted_desc = sorted(species)  # Add reverse=True
print(f"Species descending: {sorted_desc}")

Summary

In this lesson you learned:

  • Why sorting is important
  • How binary search works and why it needs a sorted list
  • Python's built-in sort() and sorted()
  • Bubble Sort, Selection Sort, Insertion Sort (O(n²))
  • Merge Sort and Quick Sort (O(n log n))
  • Sorting algorithm comparisons
  • When to use which algorithm
  • Sorting dictionaries by different criteria with key
  • Counting Sort for special cases

Checkpoint

Before moving on:

  • You understand how basic sorting algorithms work
  • You know the difference between O(n²) and O(n log n) algorithms
  • You can use sort() and sorted() with the key parameter
  • You know when to use stable sorting
  • You understand the trade-off between time and memory
  • You can choose the right algorithm for a given situation

In practice: Use Python's sort() or sorted() - they are optimized and work great in 99% of cases!

In the next lesson you will bring everything together in the Safari Species Tracker project!

Docs entries used in this lesson

Spotted a mistake in this lesson?

Check yourself

Answer the questions from this lesson. Pick an answer to see right away whether it is correct.

  1. 1. What is the worst-case time complexity of Bubble Sort?

  2. 2. What condition must a list meet for Binary Search?

  3. 3. Which sorting algorithm is the fastest for large datasets?

Hands-on tasks in the game

  • Click in order

    Click the elements in the correct order:

  • Vertical ordering

    Arrange the Binary Search steps in order:

  1. QuestionBubble Sort
  2. QuestionBinary Search
  3. QuestionAlgorithm Complexity
  4. Click in orderBuilding dict.items()
  5. Put in orderBinary Search

Useful articles