How to resolve the algorithm Sorting algorithms/Quicksort step by step in the Z80 Assembly programming language
How to resolve the algorithm Sorting algorithms/Quicksort step by step in the Z80 Assembly programming language
Table of Contents
Problem Statement
Sort an array (or list) elements using the quicksort algorithm. The elements must have a strict weak order and the index of the array can be of any discrete type. For languages where this is not possible, sort an array of integers.
Quicksort, also known as partition-exchange sort, uses these steps.
The best pivot creates partitions of equal length (or lengths differing by 1). The worst pivot creates an empty partition (for example, if the pivot is the first or last element of a sorted array). The run-time of Quicksort ranges from O(n log n) with the best pivots, to O(n2) with the worst pivots, where n is the number of elements in the array.
This is a simple quicksort algorithm, adapted from Wikipedia. A better quicksort algorithm works in place, by swapping elements within the array, to avoid the memory allocation of more arrays. Quicksort has a reputation as the fastest sort. Optimized variants of quicksort are common features of many languages and libraries. One often contrasts quicksort with merge sort, because both sorts have an average time of O(n log n). Quicksort is at one end of the spectrum of divide-and-conquer algorithms, with merge sort at the opposite end.
With quicksort, every element in the first partition is less than or equal to every element in the second partition. Therefore, the merge phase of quicksort is so trivial that it needs no mention! This task has not specified whether to allocate new arrays, or sort in place. This task also has not specified how to choose the pivot element. (Common ways to are to choose the first element, the middle element, or the median of three elements.) Thus there is a variety among the following implementations.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Sorting algorithms/Quicksort step by step in the Z80 Assembly programming language
Source code in the z80 programming language
;--------------------------------------------------------------------------------------------------------------------
; Quicksort, inputs (__sdcccall(1) calling convention):
; HL = uint16_t* A (pointer to beginning of array)
; DE = uint16_t len (number of word elements in array)
; modifies: AF, A'F', BC, DE, HL
; WARNING: array can't be aligned to start/end of 64ki address space, like HL == 0x0000, or having last value at 0xFFFE
; WARNING: stack space required is on average about 6*log(len) (depending on the data, in extreme case it may be more)
quicksort_a:
; convert arguments to HL=A.begin(), DE=A.end() and continue with quicksort_a_impl
ex de,hl
add hl,hl
add hl,de
ex de,hl
; |
; fallthrough into implementation
; |
; v
;--------------------------------------------------------------------------------------------------------------------
; Quicksort implementation, inputs:
; HL = uint16_t* A.begin() (pointer to beginning of array)
; DE = uint16_t* A.end() (pointer beyond array)
; modifies: AF, A'F', BC, HL (DE is preserved)
quicksort_a_impl:
; array must be located within 0x0002..0xFFFD
ld c,l
ld b,h ; BC = A.begin()
; if (len < 2) return; -> if (end <= begin+2) return;
inc hl
inc hl
or a
sbc hl,de ; HL = -(2*len-2), len = (2-HL)/2
ret nc ; case: begin+2 >= end <=> (len < 2)
push de ; preserve A.end() for recursion
push bc ; preserve A.begin() for recursion
; uint16_t pivot = A[len / 2];
rr h
rr l
dec hl
res 0,l
add hl,de
ld a,(hl)
inc hl
ld l,(hl)
ld h,b
ld b,l
ld l,c
ld c,a ; HL = A.begin(), DE = A.end(), BC = pivot
; flip HL/DE meaning, it makes simpler the recursive tail and (A[j] > pivot) test
ex de,hl ; DE = A.begin(), HL = A.end(), BC = pivot
dec de ; but keep "from" address (related to A[i]) at -1 as "default" state
; for (i = 0, j = len - 1; ; i++, j--) { ; DE = (A+i-1).hi, HL = A+j+1
.find_next_swap:
; while (A[j] > pivot) j--;
.find_j:
dec hl
ld a,b
sub (hl)
dec hl ; HL = A+j (finally)
jr c,.find_j ; if cf=1, A[j].hi > pivot.hi
jr nz,.j_found ; if zf=0, A[j].hi < pivot.hi
ld a,c ; if (A[j].hi == pivot.hi) then A[j].lo vs pivot.lo is checked
sub (hl)
jr c,.find_j
.j_found:
; while (A[i] < pivot) i++;
.find_i:
inc de
ld a,(de)
inc de ; DE = (A+i).hi (ahead +0.5 for swap)
sub c
ld a,(de)
sbc a,b
jr c,.find_i ; cf=1 -> A[i] < pivot
; if (i >= j) break; // DE = (A+i).hi, HL = A+j, BC=pivot
sbc hl,de ; cf=0 since `jr c,.find_i`
jr c,.swaps_done
add hl,de ; DE = (A+i).hi, HL = A+j
; swap(A[i], A[j]);
inc hl
ld a,(de)
ldd
ex af,af
ld a,(de)
ldi
ex af,af
ld (hl),a ; Swap(A[i].hi, A[j].hi) done
dec hl
ex af,af
ld (hl),a ; Swap(A[i].lo, A[j].lo) done
inc bc
inc bc ; pivot value restored (was -=2 by ldd+ldi)
; --j; HL = A+j is A+j+1 for next loop (ready)
; ++i; DE = (A+i).hi is (A+i-1).hi for next loop (ready)
jp .find_next_swap
.swaps_done:
; i >= j, all elements were already swapped WRT pivot, call recursively for the two sub-parts
dec de ; DE = A+i
; quicksort_c(A, i);
pop hl ; HL = A
call quicksort_a_impl
; quicksort_c(A + i, len - i);
ex de,hl ; HL = A+i
pop de ; DE = end() (and return it preserved)
jp quicksort_a_impl
You may also check:How to resolve the algorithm Loops/While step by step in the Bracmat programming language
You may also check:How to resolve the algorithm Web scraping step by step in the Scala programming language
You may also check:How to resolve the algorithm Read entire file step by step in the ooRexx programming language
You may also check:How to resolve the algorithm URL decoding step by step in the Oberon-2 programming language
You may also check:How to resolve the algorithm Count occurrences of a substring step by step in the EGL programming language