Module 2 Lesson 9: Sorting Techniques

Sorting is the process of arranging items in a specific order (like alphabetical or numerical). As we learned in the previous lesson, sorted data is a superpower because it allows for lightning-fast searching. In this lesson, we’ll look at how sorting works under the hood and how Python makes it easy for us.

Lesson Overview

In this lesson, we will cover:

• Bubble Sort: The "teaching" algorithm.
• The Swap Logic: How computers move things around.
• Python's Built-in Sorting: .sort() vs sorted().
• Custom Sorting: Sorting in reverse or by specific rules.

---

1. Bubble Sort (Learning the Logic)

Bubble sort is called "Bubble" because the largest elements "bubble up" to the end of the list with each pass. It works by comparing every neighbor and swapping them if they are in the wrong order.

def bubble_sort(nums):
    n = len(nums)
    # Loop through the list multiple times
    for i in range(n):
        # Last i elements are already in place
        for j in range(0, n - i - 1):
            # Swap if the element found is greater than the next element
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums

my_list = [64, 34, 25, 12, 22, 11]
print(bubble_sort(my_list)) # Output: [11, 12, 22, 25, 34, 64]

Note: Bubble Sort is great for understanding logic, but it's very slow for large lists.

---

2. Python’s Professional Sorting

In the real world, you almost never write your own sorting algorithm. Python provides two built-in tools that are incredibly fast.

A. .sort() (Modifies the Original)

Use this when you don't need the original unsorted list anymore.

fruits = ["banana", "apple", "cherry"]
fruits.sort() 
print(fruits) # Output: ['apple', 'banana', 'cherry']

B. sorted() (Creates a New List)

Use this when you want to keep your original data safe.

scores = [10, 5, 8]
new_scores = sorted(scores)
print(scores)     # Still [10, 5, 8]
print(new_scores) # [5, 8, 10]

---

3. Reverse and Custom Sorting

You can add the reverse=True argument to any of these tools to sort in descending order.

prices = [1.99, 49.99, 5.00]
prices.sort(reverse=True)
print(prices) # Output: [49.99, 5.0, 1.99]

---

Practice Exercise: The Scoreboard

Create a file named scoreboard.py.

1. Create a list of 5 sets of user data: {"name": "Alex", "score": 50}, etc. (Yes, a list of dictionaries!).
2. Use Python's sorted() function with a custom "key" to sort them by score.
   • Hint: sorted(data, key=lambda x: x["score"], reverse=True)
3. Print the top 3 players and their scores.

---

Quick Knowledge Check

1. How does Bubble Sort decide when to "swap" two items?
2. What is the main difference between .sort() and sorted()?
3. How do you sort a list in descending (reverse) order?
4. Why should you avoid writing your own sorting algorithms for large tasks?

---

Key Takeaways

• Sorting makes searching (Binary Search) possible.
• Bubble Sort is a great logic exercise but inefficient.
• Python's built-in Timsort (used in .sort() and sorted()) is world-class.
• Choosing the right sorting tool depends on whether you want to change the original data.

---

What’s Next?

We’ve seen that some algorithms (Binary Search) are faster than others (Linear Search). But how do we measure that speed mathematically? In Lesson 10, we’ll wrap up Module 2 by discussing Time Complexity (Big O) Basics!