Sorting Algorithms - Species Classification

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

1# Example: Searching in a sorted list
2species = ["Elephas", "Gorilla", "Leo", "Loxodonta", "Panthera", "Python"]
3
4# Binary search - O(log n) - but requires sorting!
5import bisect
6index = bisect.bisect_left(species, "Leo")  # Fast!
7
8# vs unsorted list - O(n)
9unsorted_species = ["Python", "Leo", "Gorilla", ...]
10index = 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.

1def binary_search(sorted_list, target):
2    left = 0
3    right = len(sorted_list) - 1
4    while left <= right:
5        mid = (left + right) // 2       # 1. middle of the range
6        if sorted_list[mid] == target:  # 2. compare
7            return mid                  # 4. found - return the position
8        elif sorted_list[mid] < target:
9            left = mid + 1              # 3. search the right half
10        else:
11            right = mid - 1             # 3. search the left half
12    return -1                           # 4. not found
13
14species = ["Elephas", "Gorilla", "Leo", "Loxodonta", "Panthera", "Python"]
15print(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# 1. list.sort() - sorts in-place (modifies original list)
2animals = ["Tiger", "Elephant", "Lion", "Parrot"]
3animals.sort()  # Modifies animals
4print(animals)  # ['Elephant', 'Lion', 'Parrot', 'Tiger']
5
6# 2. sorted() - returns a new sorted list
7animals = ["Tiger", "Elephant", "Lion", "Parrot"]
8sorted_animals = sorted(animals)  # New list
9print(animals)  # ['Tiger', 'Elephant', 'Lion', 'Parrot'] - unchanged
10print(sorted_animals)  # ['Elephant', 'Lion', 'Parrot', 'Tiger']
11
12# 3. Sorting with a key
13animals = ["Tiger", "Elephant", "Lion", "Parrot"]
14sorted_by_length = sorted(animals, key=len)
15print(sorted_by_length)  # ['Lion', 'Tiger', 'Parrot', 'Elephant']
16
17# 4. Reverse sorting
18animals.sort(reverse=True)
19print(animals)  # ['Tiger', 'Parrot', 'Lion', 'Elephant']
20
21# 5. Sorting dict by values
22species_count = {"Python": 5, "Leo": 3, "Elephas": 8}
23sorted_species = sorted(species_count.items(), key=lambda x: x[1], reverse=True)
24print(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.

1def bubble_sort(arr):
2    """
3    Bubble sort - O(n²)
4
5    Algorithm:
6    1. Go through the entire list
7    2. Compare each pair of adjacent elements
8    3. Swap them if they are in the wrong order
9    4. Repeat until nothing changes
10    """
11    n = len(arr)
12
13    for i in range(n):
14        # After each iteration the largest element "floats" to the end
15        swapped = False  # Optimization - if nothing changed, list is sorted
16
17        for j in range(0, n - i - 1):  # Skip last i elements (already sorted)
18            if arr[j] > arr[j + 1]:
19                # Swap
20                arr[j], arr[j + 1] = arr[j + 1], arr[j]
21                swapped = True
22
23        if not swapped:
24            break  # List already sorted
25
26    return arr
27
28# Example
29species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
30sorted_species = bubble_sort(species.copy())
31print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']
32
33# Step by step:
34# Pass 1: ["Leo", "Elephas", "Gorilla", "Panthera", "Python"]  # Python "floated" up
35# Pass 2: ["Elephas", "Gorilla", "Leo", "Panthera", "Python"]  # Panthera "floated" up
36# 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.

1def selection_sort(arr):
2    """
3    Selection sort - O(n²)
4
5    Algorithm:
6    1. Find the smallest element in the unsorted part
7    2. Swap it with the first element of the unsorted part
8    3. Move the sorted boundary by 1
9    4. Repeat
10    """
11    n = len(arr)
12
13    for i in range(n):
14        # Find index of smallest element in unsorted part
15        min_index = i
16        for j in range(i + 1, n):
17            if arr[j] < arr[min_index]:
18                min_index = j
19
20        # Swap smallest element with first unsorted
21        arr[i], arr[min_index] = arr[min_index], arr[i]
22
23    return arr
24
25# Example
26species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
27sorted_species = selection_sort(species.copy())
28print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']
29
30# Step by step:
31# i=0: ["Elephas", "Leo", "Python", "Gorilla", "Panthera"]  # Found min: Elephas
32# i=1: ["Elephas", "Gorilla", "Python", "Leo", "Panthera"]  # Found min: Gorilla
33# i=2: ["Elephas", "Gorilla", "Leo", "Python", "Panthera"]  # Found min: Leo
34# i=3: ["Elephas", "Gorilla", "Leo", "Panthera", "Python"]  # Found min: Panthera
35# 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.

1def insertion_sort(arr):
2    """
3    Insertion sort - O(n²)
4
5    Algorithm:
6    1. Start from the second element
7    2. Compare it with elements to the left
8    3. Shift larger elements to the right
9    4. Insert element at the right position
10    5. Repeat for each element
11    """
12    for i in range(1, len(arr)):
13        key = arr[i]  # Element to insert
14        j = i - 1
15
16        # Shift elements greater than key one position to the right
17        while j >= 0 and arr[j] > key:
18            arr[j + 1] = arr[j]
19            j -= 1
20
21        # Insert key at the right position
22        arr[j + 1] = key
23
24    return arr
25
26# Example
27species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
28sorted_species = insertion_sort(species.copy())
29print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']
30
31# Step by step:
32# i=1 (Leo):      ["Leo", "Python", "Elephas", "Gorilla", "Panthera"]
33# i=2 (Elephas):  ["Elephas", "Leo", "Python", "Gorilla", "Panthera"]
34# i=3 (Gorilla):  ["Elephas", "Gorilla", "Leo", "Python", "Panthera"]
35# 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.

1def merge_sort(arr):
2    """
3    Merge sort - O(n log n)
4
5    Algorithm (Divide and Conquer):
6    1. If list has 1 element - already sorted
7    2. Divide list into two halves
8    3. Sort each half recursively
9    4. Merge two sorted halves
10    """
11    if len(arr) <= 1:
12        return arr
13
14    # Divide
15    mid = len(arr) // 2
16    left = merge_sort(arr[:mid])
17    right = merge_sort(arr[mid:])
18
19    # Merge
20    return merge(left, right)
21
22def merge(left, right):
23    """
24    Merge two sorted lists into one sorted list
25    """
26    result = []
27    i = j = 0
28
29    # Compare elements from both lists and add the smaller one
30    while i < len(left) and j < len(right):
31        if left[i] <= right[j]:
32            result.append(left[i])
33            i += 1
34        else:
35            result.append(right[j])
36            j += 1
37
38    # Add remaining elements (one list is empty)
39    result.extend(left[i:])
40    result.extend(right[j:])
41
42    return result
43
44# Example
45species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
46sorted_species = merge_sort(species)
47print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']
48
49# Recursion tree:
50# ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
51#       /                                  \
52# ["Python", "Leo"]                  ["Elephas", "Gorilla", "Panthera"]
53#   /        \                           /                \
54# ["Python"] ["Leo"]               ["Elephas"]    ["Gorilla", "Panthera"]
55#                                                      /            \
56#                                                ["Gorilla"]    ["Panthera"]
57# Merging:
58# ["Leo", "Python"]                 ["Elephas", "Gorilla", "Panthera"]
59#                \                    /
60#         ['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.

1def quick_sort(arr):
2    """
3    Quick sort - O(n log n) average, O(n²) worst
4
5    Algorithm:
6    1. If list has ≤1 element - already sorted
7    2. Choose pivot (e.g., last element)
8    3. Divide into: smaller than pivot, equal to pivot, larger than pivot
9    4. Recursively sort smaller and larger
10    5. Combine: [sorted smaller] + [pivot] + [sorted larger]
11    """
12    if len(arr) <= 1:
13        return arr
14
15    # Choose pivot (e.g., last element)
16    pivot = arr[-1]
17
18    # Divide into 3 groups
19    smaller = [x for x in arr[:-1] if x < pivot]
20    equal = [x for x in arr if x == pivot]
21    larger = [x for x in arr[:-1] if x > pivot]
22
23    # Recursively sort and combine
24    return quick_sort(smaller) + equal + quick_sort(larger)
25
26# More efficient version (in-place):
27def quick_sort_inplace(arr, low=0, high=None):
28    """Quick sort in-place with Lomuto partitioning"""
29    if high is None:
30        high = len(arr) - 1
31
32    if low < high:
33        # Partition and get pivot index
34        pivot_index = partition(arr, low, high)
35
36        # Sort parts before and after pivot
37        quick_sort_inplace(arr, low, pivot_index - 1)
38        quick_sort_inplace(arr, pivot_index + 1, high)
39
40    return arr
41
42def partition(arr, low, high):
43    """Lomuto partitioning"""
44    pivot = arr[high]  # Choose last element as pivot
45    i = low - 1  # Index of smaller element
46
47    for j in range(low, high):
48        if arr[j] <= pivot:
49            i += 1
50            arr[i], arr[j] = arr[j], arr[i]
51
52    # Place pivot at the right position
53    arr[i + 1], arr[high] = arr[high], arr[i + 1]
54    return i + 1
55
56# Example
57species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
58sorted_species = quick_sort(species)
59print(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

When to Use Which Algorithm?

1# Small data (<50 elements) or nearly sorted
2# → Insertion Sort
3small_list = ["Python", "Leo", "Elephas"]
4insertion_sort(small_list)  # Fast for small data!
5
6# Large data, need stability
7# → Merge Sort or Python sort()
8import random
9
10large_list = [random.random() for _ in range(10000)]
11sorted_list = sorted(large_list)  # Timsort - stable!
12
13# Large data, limited memory, don't need stability
14# → Quick Sort (in-place)
15import random
16
17large_list = [random.random() for _ in range(10000)]
18quick_sort_inplace(large_list)  # Low memory!
19
20# In practice: ALWAYS use Python sort() or sorted()
21# They are optimized, stable, and very fast (Timsort)!
22animals.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):

1species_list = [
2    {"name": "Python regius", "size": 1.5, "dangerous": False},
3    {"name": "Panthera leo", "size": 2.5, "dangerous": True},
4    {"name": "Elephas maximus", "size": 3.5, "dangerous": False},
5    {"name": "Crocodylus niloticus", "size": 4.5, "dangerous": True},
6    {"name": "Gorilla gorilla", "size": 1.8, "dangerous": False}
7]
8
9# 1. Sort by name
10sorted_by_name = sorted(species_list, key=lambda s: s["name"])
11for s in sorted_by_name:
12    print(s["name"])
13# Crocodylus niloticus, Elephas maximus, Gorilla gorilla, Panthera leo, Python regius
14
15# 2. Sort by size (descending)
16sorted_by_size = sorted(species_list, key=lambda s: s["size"], reverse=True)
17for s in sorted_by_size:
18    print(f"{s['name']}: {s['size']}m")
19# Crocodylus niloticus: 4.5m, Elephas maximus: 3.5m, Panthera leo: 2.5m, ...
20
21# 3. Dangerous first, then from the largest
22sorted_by_danger_size = sorted(species_list, key=lambda s: (not s["dangerous"], -s["size"]))
23for s in sorted_by_danger_size:
24    danger = "dangerous" if s["dangerous"] else "safe"
25    print(f"{s['name']}: {s['size']}m ({danger})")
26# Crocodylus niloticus: 4.5m (dangerous)
27# Panthera leo: 2.5m (dangerous)
28# Elephas maximus: 3.5m (safe)
29# ...

Counting Sort - For Special Cases

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

1def counting_sort(arr, max_value):
2    """
3    Counting sort - O(n + k) where k = max_value
4
5    Works only for integers in range [0, max_value]
6    """
7    # Count occurrences of each number
8    count = [0] * (max_value + 1)
9    for num in arr:
10        count[num] += 1
11
12    # Build sorted list
13    sorted_arr = []
14    for num, freq in enumerate(count):
15        sorted_arr.extend([num] * freq)
16
17    return sorted_arr
18
19# Safari example: Sorting number of discoveries (0-100)
20daily_discoveries = [5, 3, 8, 3, 12, 5, 7, 3, 10, 5]
21sorted_discoveries = counting_sort(daily_discoveries, max(daily_discoveries))
22print(sorted_discoveries)  # [3, 3, 3, 5, 5, 5, 7, 8, 10, 12]
23
24# 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:

1class SpeciesCatalog:
2    """Species cataloging system with various sorts"""
3
4    def __init__(self):
5        self.species = []
6
7    def add_species(self, name, size, habitat, dangerous):
8        """Add species to catalog"""
9        self.species.append({
10            "name": name,
11            "size": size,
12            "habitat": habitat,
13            "dangerous": dangerous
14        })
15
16    def sort_by_name(self):
17        """Sort alphabetically"""
18        return sorted(self.species, key=lambda s: s["name"])
19
20    def sort_by_size(self, descending=True):
21        """Sort by size"""
22        return sorted(self.species, key=lambda s: s["size"], reverse=descending)
23
24    def sort_by_danger_then_size(self):
25        """Sort: dangerous first, then by size"""
26        return sorted(self.species, key=lambda s: (not s["dangerous"], -s["size"]))
27
28    def filter_and_sort(self, habitat=None, min_size=None, sort_by="name"):
29        """Filter and sort"""
30        filtered = self.species
31
32        if habitat:
33            filtered = [s for s in filtered if s["habitat"] == habitat]
34
35        if min_size:
36            filtered = [s for s in filtered if s["size"] >= min_size]
37
38        if sort_by == "name":
39            return sorted(filtered, key=lambda s: s["name"])
40        elif sort_by == "size":
41            return sorted(filtered, key=lambda s: s["size"], reverse=True)
42
43        return filtered
44
45# Usage
46catalog = SpeciesCatalog()
47catalog.add_species("Python regius", 1.5, "jungle", False)
48catalog.add_species("Panthera leo", 2.5, "savanna", True)
49catalog.add_species("Elephas maximus", 3.5, "jungle", False)
50catalog.add_species("Crocodylus niloticus", 4.5, "river", True)
51
52# Large jungle species sorted by size
53jungle_large = catalog.filter_and_sort(habitat="jungle", min_size=2.0, sort_by="size")
54for s in jungle_large:
55    print(f"{s['name']}: {s['size']}m")
56# 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

1# Sorting lists
2# .sort() modifies the original list, sorted() creates a new one
3
4animal_weights = [450, 120, 5000, 30, 900, 1500]
5animal_names = ["cheetah", "lion", "elephant", "zebra", "antelope", "buffalo"]
6
7# sort() - sorts in place (modifies the original list)
8animal_weights.sort()
9print(f"Weights ascending: {animal_weights}")
10
11animal_weights.sort(reverse=True)
12print(f"Weights descending: {animal_weights}")
13
14# sorted() - returns a NEW sorted list
15sorted_names = sorted(animal_names)
16print(f"\nNames alphabetically: {sorted_names}")
17print(f"Original list: {animal_names}")  # Unchanged!
18
19# TODO: Create a list of distances to a watering hole (in km)
20distances = [12.5, 3.2, 8.7, 1.1, 15.3, 6.4]
21
22# TODO: Sort distances in ascending order using .sort()
23
24
25# TODO: Display the sorted list
26print(f"Distances ascending: {distances}")
27
28# TODO: Use sorted() with reverse=True to get descending order WITHOUT changing the original list
29species = ["python", "cobra", "mamba", "anaconda", "boa"]
30sorted_desc = sorted(species)  # Add reverse=True
31print(f"Species descending: {sorted_desc}")
32

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!