Sorting Algorithms - Species Classification

Welcome again, @name! 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

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 - lighter (smaller) elements "float" to the top.

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

| Algorithm | Best | Average | Worst | Memory | Stable | |----------|-----------|--------|-----------|--------|----------| | Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ Yes | | Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | ❌ No | | Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ Yes | | Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ Yes | | Quick Sort | O(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?

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()
8large_list = [random.random() for _ in range(10000)]
9sorted_list = sorted(large_list)  # Timsort - stable!
10
11# Large data, limited memory, don't need stability
12# → Quick Sort (in-place)
13large_list = [random.random() for _ in range(10000)]
14quick_sort_inplace(large_list)  # Low memory!
15
16# In practice: ALWAYS use Python sort() or sorted()
17# They are optimized, stable, and very fast (Timsort)!
18animals.sort()  # Best choice in 99% of cases!

Sorting Custom Objects

1# Safari example: Sorting species by different criteria
2
3class Species:
4    def __init__(self, name, size, dangerous):
5        self.name = name
6        self.size = size  # meters
7        self.dangerous = dangerous
8
9species_list = [
10    Species("Python regius", 1.5, False),
11    Species("Panthera leo", 2.5, True),
12    Species("Elephas maximus", 3.5, False),
13    Species("Crocodylus niloticus", 4.5, True),
14    Species("Gorilla gorilla", 1.8, False)
15]
16
17# 1. Sort by name
18sorted_by_name = sorted(species_list, key=lambda s: s.name)
19for s in sorted_by_name:
20    print(s.name)
21# Crocodylus niloticus, Elephas maximus, Gorilla gorilla, Panthera leo, Python regius
22
23# 2. Sort by size (descending)
24sorted_by_size = sorted(species_list, key=lambda s: s.size, reverse=True)
25for s in sorted_by_size:
26    print(f"{s.name}: {s.size}m")
27# Crocodylus niloticus: 4.5m, Elephas maximus: 3.5m, Panthera leo: 2.5m, ...
28
29# 3. Sort by danger, then size
30sorted_by_danger_size = sorted(species_list, key=lambda s: (not s.dangerous, -s.size))
31for s in sorted_by_danger_size:
32    danger = "⚠️" if s.dangerous else "✓"
33    print(f"{danger} {s.name}: {s.size}m")
34# ⚠️ Crocodylus niloticus: 4.5m (dangerous + largest)
35# ⚠️ Panthera leo: 2.5m (dangerous)
36# ✓ Elephas maximus: 3.5m (safe + large)
37# ...

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

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

Write a function that sorts expeditions by:

1. Number of discovered species (descending)
2. Total distance (ascending)
3. Average temperature (descending)

Compare performance of different algorithms for 100, 1000, 10000 elements.

Summary

In this lesson you learned:

• ✅ Why sorting is important
• ✅ 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 custom objects 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 Darwin will introduce you to stacks and queues - structures for organizing expeditions! 📚🔄