nx_quicksort.nx source
↩ module page · 66 lines · 2305 B
1// nx_quicksort.nx -- Hoare quicksort (in-place, last-element pivot).
2//
3// Canonical: this is the substrate-wide canonical quicksort per
4// [[feedback-no-tool-proliferation-bit-level]]. Other primitives
5// needing quicksort MUST `import "nx_quicksort.nx"` and compose;
6// re-implementing inline is refused per the cardinal. nx_qsort.nx +
7// nx_quickselect.nx may carry distinct semantics (selection vs sort)
8// but MUST declare "Distinct from [[nx_quicksort.nx]] because: ..."
9// in their headers.
10//
11// genealogy_id: hoare_1961_quicksort
12// lineage_id: in_place_comparison_sort
13// references: Hoare 'Quicksort' CACM 4(7):321, 1961.
14// Sedgewick 1978 implementation analysis.
15// license: public_domain
16// complexity: avg O(n log n), worst O(n^2).
17//
18// Tier discipline (no bare i64 in API surface):
19// - elements: *nx_int (swappable via nx_tier.nx)
20// - indices: nx_idx (platform-pointer-width)
21// - status: nx_int (small value; not platform-mandated i64)
22// The only place `i64` appears in NishiLang source is the entrypoint
23// main() return, where the kernel exit syscall ABI mandates 64-bit.
24
25// nx_safety_envelope:
26// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
27// sil_target: SIL1
28// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
29// verdict: NOT_YET_EVALUATED
30
31import "nx_syscalls.nx"
32import "nx_tier.nx"
33
34func nx_quicksort_partition(arr: *nx_int, lo: nx_idx, hi: nx_idx) -> nx_idx {
35 let pivot: nx_int = arr[hi]
36 var i: nx_idx = lo
37 var j: nx_idx = lo
38 while j < hi {
39 if arr[j] <= pivot {
40 let tmp: nx_int = arr[i]
41 arr[i] = arr[j]
42 arr[j] = tmp
43 i = i + 1
44 }
45 j = j + 1
46 }
47 let tmp2: nx_int = arr[i]
48 arr[i] = arr[hi]
49 arr[hi] = tmp2
50 return i
51}
52
53func nx_quicksort_recur(arr: *nx_int, lo: nx_idx, hi: nx_idx) -> nx_int {
54 if lo < hi {
55 let p: nx_idx = nx_quicksort_partition(arr, lo, hi)
56 if p > 0 { nx_quicksort_recur(arr, lo, p - 1) }
57 nx_quicksort_recur(arr, p + 1, hi)
58 }
59 return 0
60}
61
62// Sort arr[0..n) in place, ascending.
63func nx_quicksort(arr: *nx_int, n: nx_idx) -> nx_int {
64 if n > 1 { nx_quicksort_recur(arr, 0, n - 1) }
65 return 0
66}