Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 41 ยท Projects and Practice

Project: Visualize Sorting and Searching Algorithms

Build an algorithm visualizer in Pygame: generators that yield each step, bar charts for bubble, insertion and selection sort, binary and ternary search, speed controls.

Pygame is not only for games. It is an excellent way to see how algorithms work: bars that swap places during a sort, or a search window that shrinks until it finds its target. Watching an algorithm run makes ideas such as "bubble sort is slow" or "binary search halves the range" click in a way that formulas do not.

The trick that makes this project easy is Python generators. Instead of running an algorithm to completion, you write it so it yields after every interesting step; the Pygame loop asks for one step per tick and draws the state in between. We will build sorting and searching visualizers; the algorithm part runs here, while the bars are drawn in your own window.

The key idea: algorithm as a generator

A normal function runs from start to finish before anything can be drawn. A generator pauses at every yield, handing control back to the caller and remembering exactly where it was.

flowchart LR
  A["Algorithm generator<br/>(yields after each step)"] -- "next()" --> L["Pygame loop"]
  L -- "state: list + highlighted indices" --> D["draw bars"]
  L --> T{"speed timer"}
  T -- "tick" --> A

The loop pulls one step at a time, so drawing, input and algorithm never block each other.

Python A generator that yields every comparison

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each yielded tuple carries everything the drawing code needs: the list, which positions to highlight and what happened. The generator never mentions Pygame.

Three sorting algorithms as generators

Bubble sort compares neighbors. Insertion sort grows a sorted prefix by sliding each new element into place. Selection sort repeatedly finds the smallest remaining element.

Python
def insertion_sort(a):
    for i in range(1, len(a)):
        j = i
        while j > 0:
            yield a, (j - 1, j), "compare"
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]
                yield a, (j - 1, j), "swap"
                j -= 1
            else:
                break
    yield a, (), "done"

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            yield a, (smallest, j), "compare"
            if a[j] < a[smallest]:
                smallest = j
        if smallest != i:
            a[i], a[smallest] = a[smallest], a[i]
            yield a, (i, smallest), "swap"
    yield a, (), "done"
Python Compare the algorithms by counting steps

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Selection sort does about the same number of comparisons whatever the input but few swaps; insertion sort does fewer comparisons than bubble sort on partly sorted data. A visualizer makes those differences visible as the bars move.

Searching: binary and ternary

Binary search needs a sorted list. It keeps a window [low, high], looks at the middle and discards the half that cannot contain the target. Ternary search splits the window in thirds; it is mostly used for finding the peak of a unimodal function, but works on sorted data too.

Python
def binary_search(a, target):
    low, high = 0, len(a) - 1
    while low <= high:
        mid = (low + high) // 2
        yield (low, mid, high), "look"
        if a[mid] == target:
            yield (low, mid, high), "found"
            return
        if a[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    yield (low, high, high), "missing"

def ternary_search(a, target):
    low, high = 0, len(a) - 1
    while low <= high:
        third = (high - low) // 3
        m1, m2 = low + third, high - third
        yield (low, m1, m2, high), "look"
        if a[m1] == target:
            yield (low, m1, m2, high), "found"; return
        if a[m2] == target:
            yield (low, m1, m2, high), "found"; return
        if target < a[m1]:
            high = m1 - 1
        elif target > a[m2]:
            low = m2 + 1
        else:
            low, high = m1 + 1, m2 - 1
    yield (low, high), "missing"
Python Watch the search window shrink

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Fifty items take at most six looks (log2 50 is about 5.6). Doubling the list adds only one more look, which is why binary search is so powerful.

The Pygame visualizer

The window code chooses an algorithm, builds the generator and advances it on a timer. Bars are rectangles whose height is proportional to the value; colour marks the compared or swapped positions.

Python
import random
import pygame

pygame.init()
W, H, N = 900, 520, 60
screen = pygame.display.set_mode((W, H))
pygame.display.set_caption("Algorithm visualizer")
font = pygame.font.Font(None, 28)
clock = pygame.time.Clock()

ALGORITHMS = {pygame.K_1: ("Bubble", bubble_sort),
              pygame.K_2: ("Insertion", insertion_sort),
              pygame.K_3: ("Selection", selection_sort)}

def new_data():
    values = list(range(1, N + 1))
    random.shuffle(values)
    return values

data, steps, name = new_data(), None, "none"
marks, action = (), ""
delay, timer = 0.02, 0.0               # seconds per step
paused = False

running = True
while running:
    dt = clock.tick(60) / 1000
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False
        elif event.type == pygame.KEYDOWN:
            if event.key in ALGORITHMS:
                data = new_data()
                name, fn = ALGORITHMS[event.key]
                steps = fn(data)
            elif event.key == pygame.K_SPACE:
                paused = not paused
            elif event.key == pygame.K_UP:
                delay = max(0.001, delay / 1.5)       # faster
            elif event.key == pygame.K_DOWN:
                delay = min(0.5, delay * 1.5)         # slower

    if steps and not paused:
        timer += dt
        while timer >= delay and steps:               # several steps per frame when fast
            timer -= delay
            try:
                _, marks, action = next(steps)
            except StopIteration:
                steps = None
                break

    screen.fill((20, 24, 34))
    bar_w = W / N
    for i, v in enumerate(data):
        colour = (110, 130, 170)
        if i in marks:
            colour = (240, 90, 90) if action == "swap" else (250, 210, 90)
        if action == "done":
            colour = (90, 210, 140)
        h = v / N * (H - 60)
        pygame.draw.rect(screen, colour, (i * bar_w + 1, H - h, bar_w - 2, h))
    label = f"{name} sort | 1,2,3 choose | Space pause | Up/Down speed | {1/delay:.0f} steps/s"
    screen.blit(font.render(label, True, (235, 235, 245)), (10, 10))
    pygame.display.flip()
pygame.quit()

Some details worth understanding:

  • The while timer >= delay loop lets very fast speeds run several algorithm steps per frame, instead of being capped to 60 per second.
  • The generator mutates data in place, so the drawing code always reads the latest list.
  • StopIteration tells you the algorithm has finished; the last yielded "done" colours every bar green first.

Make it your own

  • Add merge sort and quick sort. Both are recursive; a generator version uses yield from for the recursive calls. Highlight the pivot.
  • Count and display comparisons and swaps, as the experiment above does.
  • Play sounds: map a bar's value to the frequency of a beep for the famous "sound of sorting" effect.
  • Search visualizer: draw each element as a box, colour the active window and mark low, mid and high.
  • Graph algorithms: use a grid, and yield each visited cell for breadth-first search or A* pathfinding.
  • Test with different data: already sorted, reversed, many duplicates. Bubble sort's early exit shines on sorted input.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why write the algorithm as a generator for a visualizer?

    yield returns control after every step, so drawing and algorithm interleave without threads.
  2. 2. How many looks does binary search need, at most, for 50 sorted items?

    Each look halves the window; log2(50) is about 5.6, so six looks suffice.
  3. 3. Which condition must hold before using binary search?

    The halving step only works because order tells you which half can be discarded.
  4. 4. What does a while timer >= delay loop allow?

    At fast speeds the delay is shorter than a frame, so multiple steps must run each frame.

Summary

  • Writing an algorithm as a generator that yields state after each step lets Pygame draw it incrementally.
  • Bars with highlighted comparisons and swaps reveal the behavior of bubble, insertion and selection sort.
  • Binary and ternary search shrink a window over sorted data; log-time growth is visible in the step counts.
  • A time-based step delay and a while loop give smooth speed control.

Next: Sudoku Game