use super::is_sorted;
pub fn insertion_sort<T: Ord>(arr: &mut [T]) {
let n = arr.len();
for i in 1..n {
let mut j = i;
while j > 0 && arr[j] < arr[j - 1] {
arr.swap(j, j - 1);
j -= 1;
}
debug_assert!(is_sorted(&arr[0..i]));
}
debug_assert!(is_sorted(arr));
}
pub fn insertion_sort_x<T: Clone + Ord>(arr: &mut [T]) {
let n = arr.len();
let mut exchanges = 0;
for i in (1..n).rev() {
if arr[i] < arr[i - 1] {
arr.swap(i, i - 1);
exchanges += 1;
}
}
if exchanges == 0 {
return;
}
for i in 2..n {
let v = arr[i].clone();
let mut j = i;
while v < arr[j - 1] {
arr[j] = arr[j - 1].clone();
j -= 1;
}
arr[j] = v;
}
debug_assert!(is_sorted(arr));
}
pub fn binary_insertion_sort<T: Clone + Ord>(arr: &mut [T]) {
let n = arr.len();
for i in 1..n {
let v = arr[i].clone();
let mut lo = 0;
let mut hi = i;
while lo < hi {
let mid = lo + (hi - lo) / 2;
if v < arr[mid] {
hi = mid;
} else {
lo = mid + 1;
}
}
for j in (lo + 1..=i).rev() {
arr[j] = arr[j - 1].clone();
}
arr[lo] = v;
}
debug_assert!(is_sorted(arr));
}
pub fn selection_sort<T: Ord>(arr: &mut [T]) {
let n = arr.len();
for i in 0..n {
let mut min = i;
for j in i + 1..n {
if arr[j] < arr[min] {
min = j;
}
}
arr.swap(i, min);
debug_assert!(is_sorted(&arr[0..=i]));
}
debug_assert!(is_sorted(arr));
}
pub fn shell_sort<T: Ord>(arr: &mut [T]) {
let n = arr.len();
let mut increment = 1;
while increment < n / 3 {
increment = 3 * increment + 1;
}
while increment >= 1 {
for i in increment..n {
let mut j = i;
while j >= increment && arr[j] < arr[j - increment] {
arr.swap(j, j - increment);
j -= increment;
}
}
if cfg!(debug_assertions) {
for i in increment..n {
if arr[i] < arr[i - increment] {
panic!("did not sort correctly {}", increment)
}
}
}
increment /= 3;
}
debug_assert!(is_sorted(arr));
}
#[cfg(test)]
mod tests {
use rand::prelude::*;
use super::*;
test_sort!(
insertion_sort,
insertion_sort_x,
binary_insertion_sort,
selection_sort,
shell_sort
);
}