Algorithm

The Speed of Merge Sort Merge Sort is another highly efficient sorting algorithm that runs in optimal $O(n \log n)$ time, regardless of the initial state of the data. It is highly valued for its predictability and stability (it preserves the relative order of equal elements). The Principle: Merge Sort is a recursive algorithm that continually splits the array into two halves until it has many arrays of size one. It then merges these small, sorted arrays back together in the correct order. ...

The Drawback of Insertion Sort Insertion Sort (Part 96) is very fast for nearly sorted data, but slow for completely unsorted data because it can only move an element one position at a time. An element near the end must be swapped many times to reach the beginning. The Solution: Shell Sort Shell Sort (invented by Donald Shell) is an enhancement of Insertion Sort. It allows for large moves by sorting elements that are far apart, drastically reducing the number of total comparisons needed. ...

The Advantage of Selection Sort Both Bubble Sort (Part 94) and Insertion Sort (Part 96) frequently swap adjacent elements, leading to many memory write operations. If you are sorting data that resides on a slow medium (like a disk cache) or requires complex I/O to access, minimizing these writes is critical. Selection Sort does exactly this. The Principle: Selection Sort makes one pass over the unsorted portion of the array to select the smallest (or largest) element. It then performs only one swap to move that selected element into its final sorted position. ...

The Advantage of Insertion Sort While Quicksort (Part 95) is fastest for large, random arrays, Insertion Sort is often faster for two specific scenarios: Small Arrays: Its low overhead makes it faster than Quicksort for arrays under 20-30 elements. Nearly Sorted Arrays: It is extremely fast, running in nearly linear time ($O(n)$), if the array is already mostly sorted. The Principle: The algorithm builds the final sorted array one item at a time. It iterates through the input elements and inserts each element into its correct position within the already sorted portion of the array. ...

The Need for Quicksort While Bubble Sort (Part 94) is easy, its slow $O(n^2)$ time complexity makes it unusable for sorting large arrays. Quicksort is the fastest widely used sorting algorithm, running in $O(n \log n)$ time on average, making it ideal for sorting large high-score tables or data structures. The Principle: Quicksort uses a “divide-and-conquer” strategy: it picks an element (the pivot) and partitions the other elements into two sub-arrays according to whether they are less than or greater than the pivot. It then recursively sorts the sub-arrays. ...

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 Need for Fast Lookup If you have a large list of data (e.g., all font character pointers, or a list of game variables) that is sorted alphabetically or numerically, checking every item sequentially (`memchr′ in Part 89) is inefficient. Binary Search is the solution: it finds the target by repeatedly dividing the search space in half. The Principle: After each comparison, the algorithm eliminates half of the remaining elements. This makes the search time logarithmic, drastically speeding up large lookups. ...

The Challenge of Integer Division The Z80 CPU has no instruction for division. Every division operation must be performed using software algorithms based on repeated subtraction or shifting and subtraction (the same method used for manual long division). Goal: Divide a 16-bit number (the Dividend) by an 8-bit number (the Divisor) to produce a 16-bit Quotient and an 8-bit Remainder. The Algorithm: Binary Long Division The most efficient method is to implement the Binary Long Division algorithm, which uses shifts and conditional subtraction. ...

The Challenge: Precision and Speed Calculating the square root of a floating-point number (Part 30) is required for precise calculations like distance, physics, or graphics shading. This requires an iterative algorithm that works across the multi-byte structure of the float. Method: The Newton-Raphson Method is the preferred algorithm for floating-point square roots because it is computationally fast (it converges quadratically). The Newton-Raphson Formula The goal is to iteratively refine a guess ($x_{n+1}$) using the previous guess ($x_n$) until the guesses stop changing (convergence). ...

The Challenge of Square Roots The Z80 cannot natively calculate a square root. This complex operation must be achieved using an iterative algorithm that repeatedly guesses the answer and refines the guess until it is accurate enough. Goal: To find the largest integer $R$ such that $R^2 \le N$, where $N$ is the input number. Method 1: Integer Binary Search (The Reliable Method) The Binary Search method is the safest and most reliable way to find the integer square root on an 8-bit processor. It works by checking the midpoint of a search range. ...