forked from weihanglo/rust-algorithm-club
-
Notifications
You must be signed in to change notification settings - Fork 0
/
mod.rs
39 lines (36 loc) · 917 Bytes
/
mod.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
/// Insertion sort.
pub fn insertion_sort(arr: &mut [i32]) {
for i in 1..arr.len() {
let mut j = i;
while j > 0 && arr[j - 1] > arr[j] {
arr.swap(j - 1, j);
j -= 1;
}
}
}
/// Binary insertion sort.
///
/// Binary insertion sort is a insertion sort variant that utilizes binary
/// search to reduce comparisons in a normal insertion sort.
pub fn binary_insertion_sort(arr: &mut [i32]) {
for i in 1..arr.len() {
let val = arr[i];
let mut j = i;
let pos = arr[..i].binary_search(&val).unwrap_or_else(|pos| pos);
// Swap all elements until specific position.
while j > pos {
arr.swap(j - 1, j);
j -= 1;
}
}
}
#[cfg(test)]
mod base {
use super::*;
base_cases!(insertion_sort);
}
#[cfg(test)]
mod binary_insertion {
use super::*;
base_cases!(binary_insertion_sort);
}