Skip to content

Instantly share code, notes, and snippets.

@airled
Last active July 12, 2024 10:20
Show Gist options
  • Save airled/adeede4ae168b808b0fd35041b1b903a to your computer and use it in GitHub Desktop.
Save airled/adeede4ae168b808b0fd35041b1b903a to your computer and use it in GitHub Desktop.
Simple quicksort in rust
fn qs(a: &mut [i32]) {
if a.len() <= 1 { return; }
// track index of the first element that >= pivot (last element)
// gte = greater than or equal
let mut first_gte_index = 0;
let pivot_index = a.len() - 1;
for i in 0..pivot_index {
if a[i] >= a[pivot_index] { continue; }
a.swap(i, first_gte_index);
first_gte_index += 1;
}
a.swap(first_gte_index, pivot_index);
qs(&mut a[0..first_gte_index]);
qs(&mut a[(first_gte_index + 1)..(pivot_index + 1)]);
}
fn main() {
let mut a = [-1,0,-2,5,7,0,-6,1];
qs(&mut a);
println!("{:?}", a);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment