1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
// Copyright 2020 Andrew Todd
/*
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
//! # Badsort
//!
//! A BOGO Sort implementation I wrote when I was super bored.
#![feature(is_sorted)]
use rand::prelude::*;
/// Sorts the given list using
/// the bogosort algorithm.
///
/// # Examples
///
/// ```
/// use badsort::bogosort;
///
/// let mut arr = vec![4, 5, 2, 1, 3];
///
/// bogosort(&mut arr);
///
/// assert_eq!(arr[0], 1);
/// ```
pub fn bogosort<T: PartialOrd>(input: &mut [T]) {
if input.is_empty() {
return;
}
let mut rng = rand::thread_rng();
while !input.iter().is_sorted() {
input.shuffle(&mut rng);
}
}
#[test]
fn small_random() {
let mut test = vec![4, 2, 1, 5, 3];
let oracle = vec![1, 2, 3, 4, 5];
bogosort(&mut test);
assert_eq!(oracle, test);
}
#[test]
fn small_same() {
let mut test = vec![0;5];
let oracle = vec![0;5];
bogosort(&mut test);
assert_eq!(oracle, test);
}
#[test]
fn empty() {
let mut test: Vec<i32> = Vec::new();
let oracle: Vec<i32> = Vec::new();
sort(&mut test);
assert_eq!(oracle, test);
}
#[test]
fn small_sorted() {
let mut test = vec![1, 2, 3, 4, 5];
let oracle = vec![1, 2, 3, 4, 5];
bogosort(&mut test);
assert_eq!(oracle, test);
}