The Need for Sorting

Sorting arrays of data (e.g., high scores, tile IDs, or inventory items) is a fundamental task. While complex algorithms exist, Bubble Sort is the simplest to implement on the Z80 due to its minimal memory requirements and straightforward logic.

The Principle: Bubble Sort works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. This process is repeated until no swaps are needed, meaning the list is sorted.

The Bubble Sort Algorithm

The algorithm requires two nested loops:

  1. Outer Loop: Controls the passes over the data (since multiple passes are required).
  2. Inner Loop: Steps through the array, comparing adjacent items ($A_i$ and $A_{i+1}$).

Z80 Implementation Focus

We will focus on sorting an array of 8-bit bytes and use register pairs for the two necessary pointers:

Register Pair Purpose
HL Outer Loop Pointer (Tracks the current position $i$)
DE Inner Loop Pointer (Tracks the next position $i+1$)
B Counter (Tracks the length of the array)

The Inner Loop Logic (Simplified):

INNER_LOOP:
    LD   A, (HL)            ; A ← Get current item (i)
    CP   (DE)               ; Compare A with next item (i+1)
    
    JP   C, NO_SWAP         ; If Carry=1, current item is < next item. Order is fine.
    
    ; --- SWAP REQUIRED (A > [DE]) ---
    ; This is the critical block that swaps the values at (HL) and (DE).
    PUSH AF                 ; Save the item in A temporarily
    LD   A, (DE)            ; A &larr; Next item (i+1)
    LD   (HL), A            ; Store i+1 at position (i)
    POP  AF                 ; A &larr; Original item (i)
    LD   (DE), A            ; Store original item (i) at position (i+1)
    
NO_SWAP:
    INC  HL                 ; Advance to next comparison pair
    INC  DE
    DJNZ INNER_LOOP         ; Continue until inner loop is done

Optimization and Pitfalls

  • T-State Cost: Bubble Sort is slow, typically running in $O(n^2)$ time. For a list of 100 items, this requires roughly $10,000$ operations.
  • Optimization: A status flag must be used to track if any swaps occurred in the entire pass. If no swaps occurred, the list is sorted, and the outer loop can be terminated early.
  • 16-bit Sort: Sorting 16-bit words (like high scores or addresses) is slower because the swap and comparison logic must be performed across two bytes for each element.