-
-
Notifications
You must be signed in to change notification settings - Fork 2.3k
/
stooge_sort.rs
63 lines (53 loc) · 1.45 KB
/
stooge_sort.rs
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
fn _stooge_sort<T: Ord>(arr: &mut [T], start: usize, end: usize) {
if arr[start] > arr[end] {
arr.swap(start, end);
}
if start + 1 >= end {
return;
}
let k = (end - start + 1) / 3;
_stooge_sort(arr, start, end - k);
_stooge_sort(arr, start + k, end);
_stooge_sort(arr, start, end - k);
}
pub fn stooge_sort<T: Ord>(arr: &mut [T]) {
let len = arr.len();
if len == 0 {
return;
}
_stooge_sort(arr, 0, len - 1);
}
#[cfg(test)]
mod test {
use super::*;
use crate::sorting::have_same_elements;
use crate::sorting::is_sorted;
#[test]
fn basic() {
let mut vec = vec![3, 5, 6, 3, 1, 4];
let cloned = vec.clone();
stooge_sort(&mut vec);
assert!(is_sorted(&vec) && have_same_elements(&vec, &cloned));
}
#[test]
fn empty() {
let mut vec: Vec<i32> = vec![];
let cloned = vec.clone();
stooge_sort(&mut vec);
assert!(is_sorted(&vec) && have_same_elements(&vec, &cloned));
}
#[test]
fn reverse() {
let mut vec = vec![6, 5, 4, 3, 2, 1];
let cloned = vec.clone();
stooge_sort(&mut vec);
assert!(is_sorted(&vec) && have_same_elements(&vec, &cloned));
}
#[test]
fn already_sorted() {
let mut vec = vec![1, 2, 3, 4, 5, 6];
let cloned = vec.clone();
stooge_sort(&mut vec);
assert!(is_sorted(&vec) && have_same_elements(&vec, &cloned));
}
}