Skip to content

Instantly share code, notes, and snippets.

@ChillingHsu
Last active Nov 24, 2018
Embed
What would you like to do?
quick sort 2 way & 3 way
use std::cmp::Ordering;
fn qsort3way<T: Ord + Copy>(sli: &mut [T], lo: usize, hi: usize) {
if hi <= lo {return;}
let mut lt = lo;
let mut i = lt + 1;
let mut gt = hi;
let v = sli[lo];
while i <= gt {
match sli[i].cmp(&v) {
Ordering::Less => {
sli.swap(lt, i);
i += 1;
lt += 1;
},
Ordering::Equal => {
i += 1;
},
Ordering::Greater => {
sli.swap(gt, i);
gt -= 1;
}
}
}
qsort3way(sli, lo, lt - 1);
qsort3way(sli, gt + 1, hi);
}
fn kth<T: Ord + Clone>(sli: &mut [T], k:usize, lo: usize, hi: usize) -> Option<usize>{
if hi <= lo {return None;}
let mut i = lo + 1;
let mut j = hi;
let pivot = sli[lo].clone();
loop {
while sli[i] < pivot {
if i == hi {break;}
i += 1;
}
while pivot < sli[j] {
j -= 1;
}
if i >= j {break;}
sli.swap(i, j);
}
sli.swap(lo, j);
match k.cmp(&j) {
Ordering::Less => {
kth(sli, k + 1, lo, j - 1)
},
Ordering::Equal => {
Some(j)
},
Ordering::Greater => {
kth(sli, k - j - 1, j + 1, hi)
}
}
}
fn qsort2way<T: Ord + Copy>(sli: &mut [T], lo: usize, hi: usize) {
if hi <= lo {return;}
let mut i = lo + 1;
let mut j = hi;
let pivot = sli[lo];
loop {
while sli[i] < pivot {
if i == hi {break;}
i += 1;
}
while pivot < sli[j] {
if j == lo {break;}
j -= 1;
}
if i >= j {break;}
sli.swap(i, j);
}
sli.swap(lo, j);
if j > 0 {qsort2way(sli, lo, j - 1);}
qsort2way(sli, j + 1, hi);
}
fn main() {
let ref mut s = [3,6,7,8,5,4,1,2];
println!("{:?}", kth(s, 0, 0, 7));
println!("{:?}", s);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment