845 Fundamental

Randomized Quickselect

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Randomized Quickselect" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Finding the kth smallest element in an unsorted array naively requires sorting: O(n log n). Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Finding the kth smallest element in an unsorted array naively requires sorting: O(n log n). Quickselect finds it in O(n) expected time by using the partition step from quicksort but only recursing into one side. Choosing the pivot randomly avoids worst-case O(n^2) behavior from adversarial inputs. Practical uses: computing medians for statistics, percentile calculations in monitoring systems, streaming data analysis (p99 latency), and machine learning (median-based normalization). The deterministic variant (median-of-medians) guarantees O(n) worst-case but with higher constants.

🎯 Learning Outcomes

• Implement Lomuto or Hoare partition around a pivot, placing smaller elements left

• Choose pivot randomly to achieve O(n) expected time (not amortized — each call is O(n) expected)

• Recurse only into the side containing the target rank, halving the problem each expected step

• Understand why expected O(n): geometric series 1 + 1/2 + 1/4 + ... = 2 (expected recurrence)

• Distinguish from sorting: quickselect doesn't sort the discarded side — it literally ignores it

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Randomised Quickselect in OCaml *)

(* Simple LCG pseudo-random number generator (no dependencies) *)
let state = ref 42

let rand_int n =
  state := (!state * 1664525 + 1013904223) land 0x7fffffff;
  !state mod n

(* Partition: rearrange arr[lo..hi] around pivot, return pivot index *)
let partition (arr : int array) (lo hi : int) : int =
  let pivot_idx = lo + rand_int (hi - lo + 1) in
  let pivot = arr.(pivot_idx) in
  (* Move pivot to end *)
  let tmp = arr.(pivot_idx) in arr.(pivot_idx) <- arr.(hi); arr.(hi) <- tmp;
  let store = ref lo in
  for i = lo to hi - 1 do
    if arr.(i) < pivot then begin
      let tmp = arr.(!store) in arr.(!store) <- arr.(i); arr.(i) <- tmp;
      incr store
    end
  done;
  (* Move pivot to final position *)
  let tmp = arr.(!store) in arr.(!store) <- arr.(hi); arr.(hi) <- tmp;
  !store

(* Quickselect: find the k-th smallest (0-indexed) in arr[lo..hi] *)
let rec quickselect (arr : int array) (lo hi k : int) : int =
  if lo = hi then arr.(lo)
  else
    let p = partition arr lo hi in
    if p = k then arr.(p)
    else if p > k then quickselect arr lo (p - 1) k
    else quickselect arr (p + 1) hi k

(* Public API: k-th smallest (1-indexed) in the array *)
let kth_smallest (arr : int array) (k : int) : int =
  let copy = Array.copy arr in
  quickselect copy 0 (Array.length copy - 1) (k - 1)

(* Median of array *)
let median (arr : int array) : float =
  let n = Array.length arr in
  if n mod 2 = 1 then
    float_of_int (kth_smallest arr ((n + 1) / 2))
  else
    (float_of_int (kth_smallest arr (n / 2)) +.
     float_of_int (kth_smallest arr (n / 2 + 1))) /. 2.0

let () =
  let arr = [| 7; 10; 4; 3; 20; 15 |] in
  Printf.printf "Array: [7, 10, 4, 3, 20, 15]\n";
  for k = 1 to Array.length arr do
    Printf.printf "  %d-th smallest: %d\n" k (kth_smallest arr k)
  done;
  Printf.printf "Median: %.1f\n" (median arr);

  let arr2 = [| 1; 2; 3; 4; 5; 6; 7; 8; 9; 10 |] in
  Printf.printf "\n5th smallest of 1..10: %d (expected 5)\n" (kth_smallest arr2 5)

Key Differences

Aspect	Rust	OCaml
In-place	`&mut [i32]` slice partitioned	`array` mutation or copy
Random pivot	`rand::thread_rng()`	`Random.int n`
Three-way match	`match pivot_pos.cmp(&k)`	`compare pivot_pos k \\|> match`
Rank adjustment	`k - pivot_pos - 1`	Same arithmetic
Worst case	O(n^2) with bad pivots	Same
Deterministic	Median-of-medians variant	Same

OCaml Approach

OCaml's quickselect uses Array.swap for the Lomuto partition. Random.int n provides the random pivot. The recursive call on a sub-array uses Array.sub (copying) or passes array bounds explicitly. OCaml's compare on the pivot position drives the three-case match. The functional style returns the kth element without modifying the array by working on a copy; the in-place version uses Array.blit for subarray passing.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Randomised Quickselect in OCaml *)

(* Simple LCG pseudo-random number generator (no dependencies) *)
let state = ref 42

let rand_int n =
  state := (!state * 1664525 + 1013904223) land 0x7fffffff;
  !state mod n

(* Partition: rearrange arr[lo..hi] around pivot, return pivot index *)
let partition (arr : int array) (lo hi : int) : int =
  let pivot_idx = lo + rand_int (hi - lo + 1) in
  let pivot = arr.(pivot_idx) in
  (* Move pivot to end *)
  let tmp = arr.(pivot_idx) in arr.(pivot_idx) <- arr.(hi); arr.(hi) <- tmp;
  let store = ref lo in
  for i = lo to hi - 1 do
    if arr.(i) < pivot then begin
      let tmp = arr.(!store) in arr.(!store) <- arr.(i); arr.(i) <- tmp;
      incr store
    end
  done;
  (* Move pivot to final position *)
  let tmp = arr.(!store) in arr.(!store) <- arr.(hi); arr.(hi) <- tmp;
  !store

(* Quickselect: find the k-th smallest (0-indexed) in arr[lo..hi] *)
let rec quickselect (arr : int array) (lo hi k : int) : int =
  if lo = hi then arr.(lo)
  else
    let p = partition arr lo hi in
    if p = k then arr.(p)
    else if p > k then quickselect arr lo (p - 1) k
    else quickselect arr (p + 1) hi k

(* Public API: k-th smallest (1-indexed) in the array *)
let kth_smallest (arr : int array) (k : int) : int =
  let copy = Array.copy arr in
  quickselect copy 0 (Array.length copy - 1) (k - 1)

(* Median of array *)
let median (arr : int array) : float =
  let n = Array.length arr in
  if n mod 2 = 1 then
    float_of_int (kth_smallest arr ((n + 1) / 2))
  else
    (float_of_int (kth_smallest arr (n / 2)) +.
     float_of_int (kth_smallest arr (n / 2 + 1))) /. 2.0

let () =
  let arr = [| 7; 10; 4; 3; 20; 15 |] in
  Printf.printf "Array: [7, 10, 4, 3, 20, 15]\n";
  for k = 1 to Array.length arr do
    Printf.printf "  %d-th smallest: %d\n" k (kth_smallest arr k)
  done;
  Printf.printf "Median: %.1f\n" (median arr);

  let arr2 = [| 1; 2; 3; 4; 5; 6; 7; 8; 9; 10 |] in
  Printf.printf "\n5th smallest of 1..10: %d (expected 5)\n" (kth_smallest arr2 5)

Deep Comparison

OCaml vs Rust: Randomized Quickselect

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement median-of-medians pivot selection for guaranteed O(n) worst-case and compare speed with random pivot.

Find the top-k smallest elements (not just the kth) using quickselect plus partial sort on the left side.

Implement a streaming approximate median using the reservoir sampling or binning technique.

Measure the distribution of quickselect running time for n=10^6 across 1000 trials and compare with O(n) theory.

Implement the three-way partition (Dutch National Flag) to handle duplicate elements efficiently.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust