Coding Concepts Explained: Super Sorting Algorithms

You have a huge list of items that needs to be put in order. How do you do it? The answer lies in sorting algorithms. An algorithm is a set of rules or steps for solving a problem. Sorting is a classic computer science problem, and understanding how different algorithms work provides a fascinating insight into efficiency and performance.

💻 The Challenge of Swapping

Let’s start with the simplest case: sorting a list of two numbers, like `[8, 2]`. The logic is simple: if the first is greater than the second, swap them. But how do you swap in code? A naive approach might be:

cards = [8, 2]
if cards[0] > cards[1]:
    cards[0] = cards[1] # Now cards is [2, 2]
    cards[1] = cards[0] # Now cards is [2, 2]

This doesn’t work because we lose the original value of the first card. The correct way is to use a temporary variable to hold one of the values during the swap:

temp = cards[0]
cards[0] = cards[1]
cards[1] = temp

💻 Bubble Sort

The Bubble Sort algorithm extends this idea to a list of any size. It works by repeatedly stepping through the list, comparing each pair of adjacent items, and swapping them if they are in the wrong order. With each pass, the next largest element “bubbles” up to its correct position at the end of the list.

cards = [8, 3, 7, 4, 2, 1]
swapped = True
while swapped:
    swapped = False
    for i in range(len(cards) - 1):
        if cards[i] > cards[i+1]:
            # Python's elegant way to swap
            cards[i], cards[i+1] = cards[i+1], cards[i]
            swapped = True

The outer `while` loop keeps making passes over the list until a full pass is completed with no swaps, which means the list is sorted.

💻 Algorithm Performance and Big O Notation

Bubble sort is easy to understand, but it’s very inefficient for large lists. The amount of work it does grows exponentially as the list gets bigger. We describe this using Big O notation. Bubble sort has a worst-case performance of O(n²) (read as “O of n squared”). This means for a list of `n` items, it could take up to `n*n` operations. For a 1,000-item list, that’s a million operations! More advanced algorithms, like Quick Sort, are much faster, often performing at O(n log n).

More Topics

• Python Project Guide: NumPy & SciPy: For Science!
• Python Project Guide: Times, Dates & Numbers
• Python Project Guide: Making Scripts
• Python Project Guide: Build an FTP Client & Server
• Python Project Guide: Using Functions in Python 3
• Python Project Guide: How to Get Started with Python 3
• Coding Concepts Explained: Avoid Common Coding Mistakes