Skip to content
Tutorials Center
My learning

Topics

Lesson 51 of 57 ยท Projects

Project: Visualizing Sorting Algorithms

Record every step of bubble, insertion, merge and quick sort, draw the steps as bar-chart filmstrips, compare operation counts with Matplotlib, and animate on your computer.

Sorting algorithms are easy to describe and surprisingly hard to picture. Reading "swap neighbours if they are out of order" is one thing; watching a hundred bars rearrange themselves is another. In this project you will build a small sorting visualizer with Matplotlib. Along the way you will use a very useful programming idea: generators that yield their state so that a plot can show every step of a process.

You will build four things:

  1. A tracer for each algorithm: a function that yields the list after every step, together with the positions being touched.
  2. A filmstrip: a grid of bar charts showing snapshots of each algorithm.
  3. A cost chart: how many comparisons each algorithm needs for different input sizes.
  4. An animation (read-only code here, because the browser shows still images) for your own computer.

The big idea: a generator that yields snapshots

A normal sort function returns the sorted list at the end. A tracing sort is written as a generator: it uses yield to hand out the state of the list at every interesting moment, then carries on. The caller can draw each yielded state as one frame. Each yield carries two things: a copy of the list, and the indexes currently being compared or moved (so that we can highlight them).

flowchart LR
    A["Algorithm<br/>(generator)"] -->|"yield (list, highlighted)"| S["List of frames"]
    S --> F["Filmstrip:<br/>one bar chart per frame"]
    S --> N["Animation:<br/>one frame per tick"]
    A -->|"count comparisons"| C["Cost chart"]

One generator feeds three different pictures: a filmstrip, an animation and statistics.

Here is bubble sort written this way. Read it carefully: the only addition to the textbook version is the yield line:

Python
def bubble_sort(values):
    a = list(values)                    # work on a copy
    n = len(a)
    for end in range(n - 1, 0, -1):
        for i in range(end):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                yield a.copy(), (i, i + 1)     # snapshot after each swap
    yield a.copy(), ()                  # final, sorted state

Copying the list with a.copy() is essential. Without the copy, every frame would be the same list object and all frames would show the final result.

Four algorithms, one interface

Each of the four sorters below follows the same interface: it takes a list and yields (snapshot, highlighted_indexes). Insertion sort grows a sorted prefix by sliding each new element left. Merge sort splits the list in halves, sorts each and merges them (we write the merged values back into the list so every frame shows a full list). Quick sort picks a pivot and partitions around it.

The first example draws a filmstrip: for every algorithm, six evenly spaced frames, with the highlighted bars in orange and the finished state in green:

Python Filmstrip of four sorting algorithms

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.

Look at the picture row by row. Bubble sort moves the large bars to the right edge one by one, so the right side becomes sorted first. Insertion sort grows a sorted block on the left. Merge sort looks chaotic at first and then suddenly settles, because small pieces get sorted independently before being merged. Quick sort sorts around a pivot, so you will see values pushed to the correct side of a boundary. The assert line is a safety net: every sorter must produce the same result as Python's built-in sorted.

Tip: Testing a visualization against a known-correct answer takes one line and catches the worst bug (a pretty picture of a wrong algorithm). Keep the assert.

Counting the work

Pictures show how; numbers show how much. To compare the cost of the algorithms, count comparisons (how often two elements are compared). The counters below reuse the same logic without recording frames, so they run quickly on larger inputs:

Python Comparison counts for growing input sizes

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.

On the linear chart, bubble sort and insertion sort shoot upward like parabolas, while merge and quick sort barely lift off the floor. On the log-log chart, the pattern becomes a slope: the two quadratic algorithms (about nยฒ/2 or nยฒ/4 comparisons) follow steeper lines than merge and quick sort (about n log n). This is the practical meaning of Big O: at 320 items the quadratic sorts already need roughly ten to twenty times as many comparisons, and the gap keeps growing. See the DSA course for the theory.

Remember what a random input means: insertion sort is fast on nearly sorted data, and quick sort with a poor pivot choice on already-sorted data degrades to quadratic. A good experiment is to try np.arange(n) and np.arange(n)[::-1] as inputs and see how the numbers change.

A 3D view: the whole run in one picture

A filmstrip needs six separate charts. There is a way to show every step at once: stack the frames. Let the x axis be the position in the list, the y axis the step number (time), and the z axis the value at that position at that step. Each frame becomes one line of bars, and the whole sort becomes a landscape: you can watch the surface change from a jumble into a staircase as you read from the first step to the last. This uses the 3D tools from 3D Plots.

Collect the frames into a 2D array first: row k is the list after step k. For a long run, keep only every few steps, so that the picture stays readable.

Python Insertion sort as a 3D landscape

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.

On the left, the surface at step 0 is jagged (the shuffled values), and at the last step it is a smooth rising ramp: sorted data. Turn the view with view_init if one edge hides the other. In between you can follow the sorted prefix growing from the left. The right panel is the minimal version: two rows of 3D bars, before and after. Reading exact values from a 3D surface is hard (see When 3D hurts readability), so for analysis the same array drawn as a flat heatmap is clearer:

Python The same history as a flat heatmap

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.

Time runs along the x axis, positions up the y axis, and the colour is the value. A finished sort has a smooth gradient in the last column; the earlier columns show how quick sort shuffles values around its pivots. This heatmap works for hundreds of positions where a surface would be unreadable.

Animating on your computer

A filmstrip is the best static summary, but on your own machine you can play the frames as a movie with FuncAnimation. You pass it the list of frames; for each frame it updates the bar heights and colours. This code is read-only on this page, because the browser runner displays still images:

Python
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation

frames = list(quick_sort(data))            # any of the generators above

fig, ax = plt.subplots(figsize=(8, 4))
bars = ax.bar(range(len(data)), data, color="#60a5fa")
ax.set_xticks([])
title = ax.set_title("")

def update(k):
    state, hot = frames[k]
    for i, (bar, value) in enumerate(zip(bars, state)):
        bar.set_height(value)
        bar.set_color("#f97316" if i in hot else "#60a5fa")
    title.set_text(f"step {k} of {len(frames) - 1}")
    return list(bars) + [title]

anim = FuncAnimation(fig, update, frames=len(frames), interval=60, blit=False)
plt.show()                                  # or: anim.save("sort.gif", writer="pillow")

Updating existing bars with set_height is much faster than clearing and redrawing the whole Axes for every frame. Keep a reference to anim (here the variable) so that it is not garbage collected before it plays. See Animation Concepts for the model behind FuncAnimation and how to save GIFs and videos.

Extension ideas

  • Add selection sort and heap sort with the same (snapshot, highlighted) interface.
  • Colour the bar being used as a pivot in quick sort differently from the bars being compared.
  • Count writes (swaps) as well as comparisons and plot both.
  • Run each algorithm on four kinds of input (random, sorted, reversed, nearly sorted) and show the results as a grouped bar chart.
  • Draw the merge sort recursion as a tree with ax.annotate arrows.
  • Time the algorithms on large lists with time.perf_counter and compare with sorted, which is far faster than any pure-Python version because it is implemented in C (Timsort).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the tracing sort yield a.copy() instead of a?

    The algorithm keeps modifying one list. Yielding the list itself gives references to the same object, so every stored frame would change along with it.
  2. 2. What is the advantage of writing each algorithm as a generator that yields snapshots?

    Yielding state at each step separates the algorithm from the visualization, so you can plot or animate its steps in any way.
  3. 3. On a log-log chart of comparisons against n, which algorithms have the steepest lines?

    Quadratic growth appears as a steeper slope on a log-log chart than n log n growth.
  4. 4. Why is bar.set_height better than redrawing the Axes in every animation frame?

    Updating existing artists avoids rebuilding the whole plot for each frame.
  5. 5. What is the purpose of asserting that the last frame equals sorted(data)?

    A visualization of a wrong algorithm is misleading. A one-line correctness check keeps the project honest.

Summary

  • A tracing sort is a generator that yields (snapshot, highlighted) pairs; always yield a copy of the list.
  • One recorded list of frames feeds a filmstrip grid of bar charts, an animation, and statistics.
  • Check every tracer against sorted(data).
  • Counting comparisons for growing n and plotting on linear and log-log axes shows why n log n beats nยฒ.
  • FuncAnimation with set_height and set_color plays the frames on your own machine; keep a reference to the animation object.
  • Try different inputs (sorted, reversed, nearly sorted) to see that cost depends on the data as well as the algorithm.
  • Stacking all frames into a 2D history array gives a 3D surface (position, step, value) or a flat heatmap of the whole run.

Next: Exercises lets you practise everything in this course.