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:
- Outer Loop (Pointer $i$): Tracks the boundary between the sorted and unsorted portions of the array.
- Inner Loop (Pointer $j$): Scans the unsorted portion to find the minimum element.
The Steps (Simplified):
- Set the current element ($A_i$) as the temporary minimum.
- Scan the rest of the array ($A_{i+1}$ to end) for a smaller element.
- If a smaller element is found, update the pointer to the new minimum.
- 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.