Skip to content

Quickselect ​

Selecciona el valor en la posición zero-based k del orden ascendente sin ordenar todo el array. La entrada es un i32[]; el resultado es i32? y está ausente cuando k queda fuera del array.

tyrus
import { quickselect } from "tyrus:algorithm";

const value: i32? = quickselect([7, 1, 4, 9, 2], 2);
print(value ?? -1); // 4

Resultado de estudio ​

quickselectInfo devuelve un SelectionInfo con el snapshot de entrada original y métricas deterministas de particiones, comparaciones e intercambios.

tyrus
interface SelectionInfo {
    values: i32[];
    selected: i32?;
    rank: usize;
    comparisonCount: usize;
    swapCount: usize;
    partitionCount: usize;
}
tyrus
import { SelectionInfo, quickselectInfo } from "tyrus:algorithm";

const info: SelectionInfo = quickselectInfo([7, 1, 4, 9, 2], 2);
print(info.values); // [7, 1, 4, 9, 2]
print(info.selected ?? -1); // 4
print(info.rank); // 2
print(info.comparisonCount); // 10
print(info.swapCount); // 3
print(info.partitionCount); // 1

La complejidad media es O(n), con O(n²) en el peor caso y espacio auxiliar O(1).