This algorithm chooses 2 random numbers and, if the items in those two positions aren't ordered, swaps them. Then, it checks if the entire array is sorted.
WCS: Time O(inf), Space O(1)
Rust code:
fn better_bogo<T: Copy>(arr: Vec<T>, cond: fn(T, T) -> bool) -> Vec<T> {
let mut arr2 = arr;
'sort: loop {
let i = (rand::random::<f32>() * (arr2.len() as f32)) as usize;
let j = (rand::random::<f32>() * i as f32) as usize;
if cond(arr2[j], arr2[i]) {
let tmp: T = arr2[i];
arr2[i] = arr2[j];
arr2[j] = tmp;
}
for i in 0..(arr2.len()-1) {
if cond(arr2[i], arr2[i+1]) { continue 'sort; }
}
break 'sort;
}
return arr2;
}
Top comments (0)