---
title: "algorithm-quickselect — Mova code model"
description: "Mova code model of algorithms/src/quickselect/mod.rs: components with their labels, obernants and the model text."
url: "https://groupants.elamur.ai/free/en/mova/algorithms/src/quickselect/mod.rs.groupant/"
---
Elamur: [Mova](https://md.mova.elamur.ai/free/en/) · [Dictionary](https://md.dictionary.elamur.ai/free/en/) · [Research](https://md.research.elamur.ai/free/en/) · **Groupants**

This page as HTML: <https://groupants.elamur.ai/free/en/mova/algorithms/src/quickselect/mod.rs.groupant/>

# algorithm-quickselect

The groupant beside algorithms/src/quickselect/mod.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.

## Facts

- **kind:** groupant
- **status:** partial descriptive instance
- **source:** [`algorithms/src/quickselect/mod.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/quickselect/mod.rs)
- **source SHA-256:** `12219158d4469b4f…`
- **repository folder:** [`algorithms/src/quickselect/mod.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/quickselect/mod.rs.groupant)
- **repository commit:** `855da7bd4a7b`

> **Implementation material.** A Mova code model describes this code at one source revision: partial models, finite checks and their stated scope. It is not a reviewed general exposition, and its labels are shown as written, never raised.

## Components

| component | label | where |
|---|---|---|
| **approximant** | partial | [approximant](#approximant) |
| **ast** | partial | `syntax.json` |
| **descriptant** | present | [descriptant](#descriptant) |
| **invariant** | partial | [approximant](#approximant) |
| **tests** | existing checks referenced | [checks](#checks) |

## Obernants

The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.

| id | type | label | where |
|---|---|---|---|
| `behavior_complement` | behavior_complement | partial source derived model | [behavior_complement](#behavior-complement) |
| `reverse_reconstruction` | reverse_reconstruction | partial source derived model | [reverse_reconstruction](#reverse-reconstruction) |
| `interval_progress` | interval_progress | partial source derived model | [interval_progress](#interval-progress) |
| `duplicate_rank_fiber` | duplicate_rank_fiber | partial source derived model | [duplicate_rank_fiber](#duplicate-rank-fiber) |
| `resource_bound` | resource_bound | partial source derived model | [resource_bound](#resource-bound) |

## Rust approximants

| id | metric | error | assurance |
|---|---|---|---|
| `quickselect-1pct` | distance(index, returned value sorted-rank interval)/input_length | 1 % cap, 1 % stated | per_input_certificate |
| `quickselect-2pct` | distance(index, returned value sorted-rank interval)/input_length | 2 % cap, 2 % stated | per_input_certificate |
| `quickselect-5pct` | distance(index, returned value sorted-rank interval)/input_length | 5 % cap, 5 % stated | per_input_certificate |
| `quickselect-10pct` | distance(index, returned value sorted-rank interval)/input_length | 10 % cap, 10 % stated | per_input_certificate |

## Model text


### descriptant

#### quickselect mod groupant

Epoch 2026-10-29: prospective predictions saved outside repository before
implementation. Original std-only code/fixtures; four algorithm tests pass
twice. Compiled red control: reverse strict partition comparison.

Combiner: source identity, recurrence, invariant and checks constrain a
conditional model. Complement and converse answer different questions; no
additive inverse identity. Syntax is partial with opaque macros and no type
or name resolution. Finite evidence is not proof of all inputs or parent wiring.
Lawful Ord and successful execution are assumed; trait panics and allocation
failures are outside successful-call semantics. Preserve these observations
in future epochs. No runtime speedup claim.

### approximant

#### Forward, invariant and cost

Move midpoint pivot to last, partition strict-less values, retain side containing rank.

Invariant: Rank stays in shrinking interval; removed sides constrain selection and swaps preserve multiset.

Cost: O(n²) worst time, O(1) auxiliary space; invalid rank O(1).

### models

## Selection typed models

Subject/revision: mod.rs at manifest SHA. Observe complete successful calls
under lawful stable Ord. Trait panics are outside the successful-call model.
Partial source-derived claims have bounded evidence, not universal proofs.

### behavior_complement

U=(input x,rank k,output slice y,optional selected value r).
For k>=|x|, all outcomes except unchanged y=x,r=None are absent.
For valid k, exclude changed multiset, wrong sorted-rank value, prefix element
greater than y[k], or suffix element less than y[k]. This is the contract
complement; multiple valid within-partition arrangements remain allowed.
Reversed partition comparison fails exhaustive_all_ranks_and_partitions.

### reverse_reconstruction

Fix valid k and observed v. Compatible sequences contain v and satisfy
count(values<v)<=k<count(values<=v). Observing the full mutated slice further
fixes the multiset, without recovering original order. Invalid None with
unchanged y gives x=y and k>=|y|. Finite tests support these rank fibers;
complete preimage execution is not implemented.

### interval_progress

Type: decreasing_variant. The active interval contains k; removed sides
constrain the eventual selection. Move midpoint pivot to end, collect values
strictly less than pivot, then place pivot at boundary. A nonreturning step
removes pivot and one side, strictly decreasing interval length even on equal
values. Source reasoning supplies this model; equal-input tests exercise it.

### duplicate_rank_fiber

Type: equality_rank_interval. For fixed multiset with a values smaller than v
and e values equal to v, all k in [a,a+e) select an Ord-equivalent v. Fixed
input yields deterministic behavior, but no stable order or canonical identity
among distinguishable equal-key values is promised. Exhaustive ternary tests
exercise every rank and duplicate counts.

### resource_bound

Type: adversarial_cost. Each partition scans O(m) and removes at least one.
Sum of active lengths is O(n²); equal inputs at high ranks realize slow progress.
Auxiliary space O(1), no recursion/allocation. Invalid rank O(1), no swaps.
No randomized expected-linear claim or benchmark conclusion is made.

### checks

#### Evidence, 2026-10-29

Four tests for this algorithm passed twice with temporary local crate exports:
66 total tests, identical normalized outcomes. Strict all-target Clippy and
rustfmt passed. Temporary exports are not committed.

Coverage: 3280 ternary arrays length 0..7, 24604 rank attempts including invalid endpoints; seeded 516 full-width entries and sorted/reverse/equal vectors.

External mutant (reverse strict partition comparison) compiled; exactly one filtered new exhaustive test
failed an assertion with exit 101. No mutant committed. One red control is not
mutation completeness. Parent owns final exports, registry and source bindings.