Algorithms: Selection

Algorithms: Selection

Explore algorithms: selection code snippets and tutorials

Algorithms: Selection

Quickselect in Java

Quickselect finds a zero-based order statistic without fully sorting the input..

java 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
// Quickselect in Java
//
// PURPOSE
// Quickselect finds a zero-based order statistic without fully sorting the input.
//
// METHOD
// Partition around the middle-position pivot using a three-way partition. Retain only the
// side containing rank k, or return the pivot when k lies in the equal region.
//
// COMPLEXITY
// O(n) expected time for random input; O(n squared) worst case for this deterministic pivot.
// O(1) auxiliary space.
//
// CONTRACT
// 0 <= k < n. Mutates input. Returns the kth smallest value, counting duplicates.
// Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
// counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
// Sorted order, correct tree topology, and caller-owned data-structure invariants are
// preconditions; checking them on every query would change query complexity.
// Scalar and shape checks are included. Value-range checks are included where needed to
// prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
// workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
// uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
// partly updated after arithmetic failure. These are single-threaded, in-memory
// implementations.
//
// LANGUAGE DETAILS
// Java 17+: primitive int arrays, Arrays.binarySearch for LIS, and Math exact arithmetic.
// Invalid input throws IllegalArgumentException; arithmetic overflow throws
// ArithmeticException.
//
// EXAMPLE
// Expected return: 5.
// Expected a after call: [2, 2, 5, 7, 9].
// Run: javac AlgorithmExample.java && java AlgorithmExample
// Tests for this exact source artifact run before publication. The accompanying source
// archive includes unit cases, runtime results, and source hashes.

class AlgorithmExample {
    static void alg_require(boolean valid) { if (!valid) throw new IllegalArgumentException("invalid algorithm input"); }
    static int alg_size(int n) { alg_require(n>=0 && n<=4000000); return n; }

    static int quickselect(int[] a, int k) {
        java.util.Objects.requireNonNull(a, "a");
        int n = a.length;
        alg_require(((n >= 0) && (n <= 1000000)));
        alg_require((a.length == n));
        alg_require(((k >= 0) && (k < n)));
        int low = 0;
        int high = Math.subtractExact(n, 1);
        int left = 0;
        int mid = 0;
        int right = 0;
        int pivot = 0;
        int temp = 0;
        while ((low <= high)) {
            pivot = a[Math.addExact(low, (Math.subtractExact(high, low) / 2))];
            left = low;
            mid = low;
            right = high;
            while ((mid <= right)) {
                if ((a[mid] < pivot)) {
                    temp = a[left];
                    a[left] = a[mid];
                    a[mid] = temp;
                    left = Math.addExact(left, 1);
                    mid = Math.addExact(mid, 1);
                } else {
                    if ((a[mid] > pivot)) {
                        temp = a[mid];
                        a[mid] = a[right];
                        a[right] = temp;
                        right = Math.subtractExact(right, 1);
                    } else {
                        mid = Math.addExact(mid, 1);
                    }
                }
            }
            if ((k < left)) {
                high = Math.subtractExact(left, 1);
            } else {
                if ((k > right)) {
                    low = Math.addExact(right, 1);
                } else {
                    return pivot;
                }
            }
        }
        return Math.negateExact(1);
    }

    public static void main(String[] args) {
        int[] a = new int[] {7, 2, 9, 2, 5};
        int k = 2;
        int result = quickselect(a, k);
        System.out.println(result);
        // Expected a: [2, 2, 5, 7, 9]
        System.out.println(java.util.Arrays.toString(a));
    }
}
Nov 15, 2026 Java
Algorithms: Selection

Quickselect in JavaScript

Quickselect finds a zero-based order statistic without fully sorting the input..

javascript 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
"use strict";
// Quickselect in JavaScript
//
// PURPOSE
// Quickselect finds a zero-based order statistic without fully sorting the input.
//
// METHOD
// Partition around the middle-position pivot using a three-way partition. Retain only the
// side containing rank k, or return the pivot when k lies in the equal region.
//
// COMPLEXITY
// O(n) expected time for random input; O(n squared) worst case for this deterministic pivot.
// O(1) auxiliary space.
//
// CONTRACT
// 0 <= k < n. Mutates input. Returns the kth smallest value, counting duplicates.
// Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
// counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
// Sorted order, correct tree topology, and caller-owned data-structure invariants are
// preconditions; checking them on every query would change query complexity.
// Scalar and shape checks are included. Value-range checks are included where needed to
// prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
// workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
// uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
// partly updated after arithmetic failure. These are single-threaded, in-memory
// implementations.
//
// LANGUAGE DETAILS
// Node.js 18+: Int32Array inputs and workspaces provide compact integer storage. Automatic
// lengths and checked arithmetic reject values outside signed 32-bit. Invalid inputs or
// overflow throw RangeError.
//
// EXAMPLE
// Expected return: 5.
// Expected a after call: [2, 2, 5, 7, 9].
// Run: node example.js
// Tests for this exact source artifact run before publication. The accompanying source
// archive includes unit cases, runtime results, and source hashes.

function alg_require(valid) { if (!valid) throw new RangeError("invalid algorithm input"); }
function alg_checked(v) { if (!Number.isInteger(v) || v < -2147483648 || v > 2147483647) throw new RangeError("32-bit result overflow"); return v; }
function alg_add(a,b) { return alg_checked(a+b); }
function alg_sub(a,b) { return alg_checked(a-b); }
function alg_mul(a,b) { return alg_checked(a*b); }
function alg_size(n) { alg_require(Number.isInteger(n) && n>=0 && n<=4000000); return n; }

function quickselect(a, k) {
    alg_require(a instanceof Int32Array);
    alg_require(Number.isInteger(k) && k >= -2147483648 && k <= 2147483647);
    let n = a.length;
    alg_require(((n >= 0) && (n <= 1000000)));
    alg_require((a.length == n));
    alg_require(((k >= 0) && (k < n)));
    let low = 0;
    let high = alg_sub(n, 1);
    let left = 0;
    let mid = 0;
    let right = 0;
    let pivot = 0;
    let temp = 0;
    while ((low <= high)) {
        pivot = a[alg_add(low, Math.floor(alg_sub(high, low) / 2))];
        left = low;
        mid = low;
        right = high;
        while ((mid <= right)) {
            if ((a[mid] < pivot)) {
                temp = a[left];
                a[left] = a[mid];
                a[mid] = temp;
                left = alg_add(left, 1);
                mid = alg_add(mid, 1);
            } else {
                if ((a[mid] > pivot)) {
                    temp = a[mid];
                    a[mid] = a[right];
                    a[right] = temp;
                    right = alg_sub(right, 1);
                } else {
                    mid = alg_add(mid, 1);
                }
            }
        }
        if ((k < left)) {
            high = alg_sub(left, 1);
        } else {
            if ((k > right)) {
                low = alg_add(right, 1);
            } else {
                return pivot;
            }
        }
    }
    return alg_sub(0, 1);
}

let a = new Int32Array([7, 2, 9, 2, 5]);
let k = 2;
let result = quickselect(a, k);
console.log(result);
// Expected a: [2, 2, 5, 7, 9]
console.log(Array.from(a));
Nov 15, 2026 javascript
Algorithms: Selection

Quickselect in Python

Quickselect finds a zero-based order statistic without fully sorting the input..

python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
from bisect import bisect_left

# Quickselect in Python
#
# PURPOSE
# Quickselect finds a zero-based order statistic without fully sorting the input.
#
# METHOD
# Partition around the middle-position pivot using a three-way partition. Retain only the
# side containing rank k, or return the pivot when k lies in the equal region.
#
# COMPLEXITY
# O(n) expected time for random input; O(n squared) worst case for this deterministic pivot.
# O(1) auxiliary space.
#
# CONTRACT
# 0 <= k < n. Mutates input. Returns the kth smallest value, counting duplicates.
# Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
# counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
# Sorted order, correct tree topology, and caller-owned data-structure invariants are
# preconditions; checking them on every query would change query complexity.
# Scalar and shape checks are included. Value-range checks are included where needed to
# prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
# workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
# uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
# partly updated after arithmetic failure. These are single-threaded, in-memory
# implementations.
#
# LANGUAGE DETAILS
# Python 3.9+: automatic lengths, native lists, arbitrary-precision arithmetic, and
# bisect_left for LIS. Invalid scalar/shape inputs raise ValueError. Integer element types
# and sorted/tree invariants remain caller preconditions.
#
# EXAMPLE
# Expected return: 5.
# Expected a after call: [2, 2, 5, 7, 9].
# Run: python example.py
# Tests for this exact source artifact run before publication. The accompanying source
# archive includes unit cases, runtime results, and source hashes.

def alg_require(condition):
    if not condition:
        raise ValueError("invalid algorithm input; see contract")
def alg_size(n):
    alg_require(0 <= n <= 4000000)
    return n

def quickselect(a: list[int], k: int) -> int:
    alg_require(isinstance(a, list) and len(a) <= 1000000)
    alg_require(type(k) is int and -2147483648 <= k <= 2147483647)
    n: int = len(a)
    alg_require(n >= 0 and n <= 1000000)
    alg_require(len(a) == n)
    alg_require(k >= 0 and k < n)
    low: int = 0
    high: int = n - 1
    left: int = 0
    mid: int = 0
    right: int = 0
    pivot: int = 0
    temp: int = 0
    while low <= high:
        pivot = a[low + (high - low) // 2]
        left = low
        mid = low
        right = high
        while mid <= right:
            if a[mid] < pivot:
                temp = a[left]
                a[left] = a[mid]
                a[mid] = temp
                left += 1
                mid += 1
            elif a[mid] > pivot:
                temp = a[mid]
                a[mid] = a[right]
                a[right] = temp
                right -= 1
            else:
                mid += 1
        if k < left:
            high = left - 1
        elif k > right:
            low = right + 1
        else:
            return pivot
    return -1

a = [7, 2, 9, 2, 5]
k = 2
result = quickselect(a, k)
print(result)
# Expected a: [2, 2, 5, 7, 9]
print(a)
Nov 15, 2026 python
Algorithms: Selection

Quickselect in C

Quickselect finds a zero-based order statistic without fully sorting the input..

c 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <limits.h>
#include <errno.h>
// Quickselect in C
//
// PURPOSE
// Quickselect finds a zero-based order statistic without fully sorting the input.
//
// METHOD
// Partition around the middle-position pivot using a three-way partition. Retain only the
// side containing rank k, or return the pivot when k lies in the equal region.
//
// COMPLEXITY
// O(n) expected time for random input; O(n squared) worst case for this deterministic pivot.
// O(1) auxiliary space.
//
// CONTRACT
// 0 <= k < n. Mutates input. Returns the kth smallest value, counting duplicates.
// Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
// counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
// Sorted order, correct tree topology, and caller-owned data-structure invariants are
// preconditions; checking them on every query would change query complexity.
// Scalar and shape checks are included. Value-range checks are included where needed to
// prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
// workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
// uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
// partly updated after arithmetic failure. These are single-threaded, in-memory
// implementations.
//
// LANGUAGE DETAILS
// C99: checked calloc/free workspace, const input pointers, explicit size_t lengths. Errors
// return INT_MIN with errno=EINVAL, ERANGE, or ENOMEM. Check errno before using a result.
// Input/output arrays must not alias. No variable-length stack arrays.
//
// EXAMPLE
// Expected return: 5.
// Expected a after call: [2, 2, 5, 7, 9].
// Run: gcc -std=c99 -O2 example.c -o example && ./example
// Tests for this exact source artifact run before publication. The accompanying source
// archive includes unit cases, runtime results, and source hashes.

static int alg_min(int a, int b) { return a < b ? a : b; }
static int alg_max(int a, int b) { return a > b ? a : b; }
static int alg_checked(int64_t v, int *error) {
    if (v < INT_MIN || v > INT_MAX) { *error = 1; return 0; }
    return (int)v;
}
static int alg_add(int a, int b, int *e) { return alg_checked((int64_t)a+b,e); }
static int alg_sub(int a, int b, int *e) { return alg_checked((int64_t)a-b,e); }
static int alg_mul(int a, int b, int *e) { return alg_checked((int64_t)a*b,e); }

int quickselect(int *a, size_t a_length, int k) {
    int alg_error = 0;
    int alg_result = INT_MIN;
    errno = 0;
    if (a_length > 1000000 || (a_length && !a)) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    int n = (int)a_length;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((n >= 0) && (n <= 1000000)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((int)a_length == n))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((k >= 0) && (k < n)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int low = 0;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int high = alg_sub(n, 1, &alg_error);
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int left = 0;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int mid = 0;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int right = 0;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int pivot = 0;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int temp = 0;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    while (1) {
        int alg_condition = (low <= high);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        if (!alg_condition) break;
        pivot = a[alg_add(low, (alg_sub(high, low, &alg_error) / 2), &alg_error)];
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        left = low;
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        mid = low;
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        right = high;
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        while (1) {
            int alg_condition = (mid <= right);
            if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
            if (!alg_condition) break;
            int alg_condition_1 = (a[mid] < pivot);
            if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
            if (alg_condition_1) {
                temp = a[left];
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                a[left] = a[mid];
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                a[mid] = temp;
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                left = alg_add(left, 1, &alg_error);
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                mid = alg_add(mid, 1, &alg_error);
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
            } else {
                int alg_condition_2 = (a[mid] > pivot);
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                if (alg_condition_2) {
                    temp = a[mid];
                    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                    a[mid] = a[right];
                    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                    a[right] = temp;
                    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                    right = alg_sub(right, 1, &alg_error);
                    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                } else {
                    mid = alg_add(mid, 1, &alg_error);
                    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                }
            }
        }
        int alg_condition_3 = (k < left);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        if (alg_condition_3) {
            high = alg_sub(left, 1, &alg_error);
            if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        } else {
            int alg_condition_4 = (k > right);
            if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
            if (alg_condition_4) {
                low = alg_add(right, 1, &alg_error);
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
            } else {
                alg_result = pivot;
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                goto alg_cleanup;
            }
        }
    }
    alg_result = alg_sub(0, 1, &alg_error);
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    goto alg_cleanup;
alg_cleanup:
    return alg_result;
}

int main(void) {
    int a[] = {7, 2, 9, 2, 5};
    int k = 2;
    int result = quickselect(a, 5, k);
    printf("%d\n", result);
    // Expected a: [2, 2, 5, 7, 9]
    for (int alg_print = 0; alg_print < 5; alg_print++) printf("%d ", a[alg_print]);
    printf("\n");
    if (errno) { perror("algorithm"); return 1; }
    return 0;
}
Nov 15, 2026 C
Algorithms: Selection

Quickselect in C++

Quickselect finds a zero-based order statistic without fully sorting the input..

cpp 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <cstdint>
#include <limits>
// Quickselect in C++
//
// PURPOSE
// Quickselect finds a zero-based order statistic without fully sorting the input.
//
// METHOD
// Partition around the middle-position pivot using a three-way partition. Retain only the
// side containing rank k, or return the pivot when k lies in the equal region.
//
// COMPLEXITY
// O(n) expected time for random input; O(n squared) worst case for this deterministic pivot.
// O(1) auxiliary space.
//
// CONTRACT
// 0 <= k < n. Mutates input. Returns the kth smallest value, counting duplicates.
// Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
// counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
// Sorted order, correct tree topology, and caller-owned data-structure invariants are
// preconditions; checking them on every query would change query complexity.
// Scalar and shape checks are included. Value-range checks are included where needed to
// prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
// workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
// uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
// partly updated after arithmetic failure. These are single-threaded, in-memory
// implementations.
//
// LANGUAGE DETAILS
// C++17: const vector references for inputs, mutable references for outputs, RAII workspace,
// standard lower_bound for LIS. Invalid inputs throw invalid_argument; overflow throws
// overflow_error; allocation failure propagates bad_alloc.
//
// EXAMPLE
// Expected return: 5.
// Expected a after call: [2, 2, 5, 7, 9].
// Run: g++ -std=c++17 -O2 example.cpp -o example && ./example
// Tests for this exact source artifact run before publication. The accompanying source
// archive includes unit cases, runtime results, and source hashes.

static int alg_min(int a, int b) { return a < b ? a : b; }
static int alg_max(int a, int b) { return a > b ? a : b; }
static void alg_require(bool valid) { if (!valid) throw std::invalid_argument("invalid algorithm input"); }
static int alg_checked(int64_t v) { if (v < INT32_MIN || v > INT32_MAX) throw std::overflow_error("32-bit result overflow"); return (int)v; }
static int alg_add(int a,int b) { return alg_checked((int64_t)a+b); }
static int alg_sub(int a,int b) { return alg_checked((int64_t)a-b); }
static int alg_mul(int a,int b) { return alg_checked((int64_t)a*b); }
static size_t alg_size(int n) { alg_require(n>=0 && n<=4000000); return (size_t)n; }

int quickselect(std::vector<int>& a, int k) {
    alg_require(a.size() <= 1000000);
    int n = (int)a.size();
    alg_require(((n >= 0) && (n <= 1000000)));
    alg_require(((int)a.size() == n));
    alg_require(((k >= 0) && (k < n)));
    int low = 0;
    int high = alg_sub(n, 1);
    int left = 0;
    int mid = 0;
    int right = 0;
    int pivot = 0;
    int temp = 0;
    while ((low <= high)) {
        pivot = a[alg_add(low, (alg_sub(high, low) / 2))];
        left = low;
        mid = low;
        right = high;
        while ((mid <= right)) {
            if ((a[mid] < pivot)) {
                temp = a[left];
                a[left] = a[mid];
                a[mid] = temp;
                left = alg_add(left, 1);
                mid = alg_add(mid, 1);
            } else {
                if ((a[mid] > pivot)) {
                    temp = a[mid];
                    a[mid] = a[right];
                    a[right] = temp;
                    right = alg_sub(right, 1);
                } else {
                    mid = alg_add(mid, 1);
                }
            }
        }
        if ((k < left)) {
            high = alg_sub(left, 1);
        } else {
            if ((k > right)) {
                low = alg_add(right, 1);
            } else {
                return pivot;
            }
        }
    }
    return alg_sub(0, 1);
}

int main(void) {
    std::vector<int> a = {7, 2, 9, 2, 5};
    int k = 2;
    int result = quickselect(a, k);
    printf("%d\n", result);
    // Expected a: [2, 2, 5, 7, 9]
    for (int alg_print = 0; alg_print < 5; alg_print++) printf("%d ", a[alg_print]);
    printf("\n");
    return 0;
}
Nov 15, 2026 C++