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 Selection Sort Algorithm

The algorithm requires two nested loops:

  1. Outer Loop (Pointer $i$): Tracks the boundary between the sorted and unsorted portions of the array.
  2. Inner Loop (Pointer $j$): Scans the unsorted portion to find the minimum element.

The Steps (Simplified):

  1. Set the current element ($A_i$) as the temporary minimum.
  2. Scan the rest of the array ($A_{i+1}$ to end) for a smaller element.
  3. If a smaller element is found, update the pointer to the new minimum.
  4. After the inner loop finishes, swap the element at $A_i$ with the element at the minimum pointer (one swap per outer loop iteration).

Z80 Implementation Focus

This routine requires careful management of three 16-bit pointers: the Current Position pointer, the Minimum pointer (which holds the address of the smallest item found so far), and the Scan pointer.

The Inner Loop Logic (Simplified):

MIN_SEARCH_LOOP:
    ; Assume HL = Scan Pointer, DE = Minimum Pointer (address of smallest found so far)
    
    LD   A, (HL)            ; A ← Current item (HL)
    CP   (DE)               ; Compare A with the value at the Minimum Pointer
    
    JP   C, NEW_MINIMUM_FOUND ; If Carry=1, the item at (HL) is smaller than the current minimum
    
    JP   CONTINUE_SCAN

NEW_MINIMUM_FOUND:
    PUSH HL                 ; Temporarily save HL
    POP  DE                 ; DE ← HL (DE now points to the new minimum address)

CONTINUE_SCAN:
    INC  HL                 ; Move to the next item to scan
    ; ... (Check array bounds and JP MIN_SEARCH_LOOP)
    
    RET

Final Swap

After the inner loop completes, the routine calls a swap routine to exchange the values at the start address (the current position $i$) and the address stored in the Minimum Pointer (`DE′).

Efficiency Trade-off: Selection Sort is $O(n^2)$, just like Bubble Sort. However, since the expensive memory write operation is performed only once per pass, it is faster in environments where memory write time far exceeds CPU cycle time.