DEV Community

Nif
Nif

Posted on

Better Bogo Sort

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;
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)