pub fn selection_sort<T:Ord>(arr:&mut [T]) {
let len = arr.len();
for left in 0..len {
let mut smallest = left;
for right in (left+1)..len {
if arr[right] < arr[smallest] {
smallest = right;
}
}
arr.swap(smallest, left);
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn basic() {
let mut res = vec!["f","d","e","a","c","b"];
selection_sort(&mut res);
assert_eq!(res, vec!["a","b","c","d","e","f"]);
}
#[test]
fn empty() {
let mut res = Vec::<u8>::new();
selection_sort(&mut res);
assert_eq!(res, vec![]);
}
#[test]
fn one_element() {
let mut res = vec!["a"];
selection_sort(&mut res);
assert_eq!(res, vec!["a"]);
}
#[test]
fn pre_sorted() {
let mut res = vec!["a","b","c","d"];
selection_sort(&mut res);
assert_eq!(res, vec!["a","b","c","d"]);
}
}
pub fn bubble_sort<T:Ord>(arr:&mut [T]) {
if arr.is_empty() {
return;
}
let mut sorted = false;
let mut n = arr.len();
while!sorted {
sorted = true;
for i in 0..n-1{
if arr[i] > arr[i+1] {
arr.swap(i,i+1);
sorted = false;
}
}
n -= 1;
}
}
#[cfg(test)]
mod tests {
use super::super::is_sorted;
use super::*;
#[test]
fn descending() {
let mut vec1 = vec![6,5,4,3,2,1];
bubble_sort(&mut vec1);
assert!(is_sorted(&vec1))
}
#[test]
fn ascending() {
let mut vec2 = vec![1,2,3,4,5];
bubble_sort(&mut vec2);
assert!(is_sorted(&vec2))
}
#[test]
fn empty() {
let mut vec3:Vec<usize> = vec![];
bubble_sort(&mut vec3);
assert!(is_sorted(&vec3))
}
}
pub fn insertion_sort<T>(arr:&mut [T])
where
T: PartialOrd+Copy
{
for i in 1..arr.len() {
let cur = arr[i];
let mut j = i - 1;
while arr[j] > cur {
arr[j+1] = arr[j];
if j == 0 {
break;
}
j -= 1;
}
// exit the loop from that break statement
if j == 0 && arr[0] > cur {
arr[0] = cur;
}else {
// `arr[j]>cur` is not satisfied ,exit from condition judgement
arr[j+1] =cur;
}
}
}
#[cfg(test)]
mod tests {
use super::super::is_sorted;
use super::*;
#[test]
fn empty() {
let mut arr:[u8;0] = [];
insertion_sort(&mut arr);
assert!(is_sorted(&arr));
}
#[test]
fn one_element() {
let mut arr:[char;1] = ['a'];
insertion_sort(&mut arr);
assert!(is_sorted(&arr));
}
#[test]
fn already_sorted() {
let mut arr:[&str;3] = ["a","b","c"];
insertion_sort(&mut arr);
assert!(is_sorted(&arr));
}
#[test]
fn basic() {
let mut arr:[&str;4] = ["d","a","c","b"];
insertion_sort(&mut arr);
assert!(is_sorted(&arr));
}
#[test]
fn repeated_elements() {
let mut arr: Vec<usize> = vec![542,542,542,542];
insertion_sort(&mut arr);
assert!(is_sorted(&arr));
}
}
fn merge<T:Ord+Copy>(arr:&mut [T],mid:usize) {
// Create temporary vectors to support the merge
let left_half = arr[..mid].to_vec();
let right_half = arr[mid..].to_vec();
let mut l:usize = 0;
let mut r:usize = 0;
for v in arr {
if r == right_half.len() || (l < left_half.len() && left_half[l] < right_half[r]) {
*v = left_half[l];
l += 1;
}else {
*v = right_half[r];
r += 1;
}
}
}
pub fn top_down_merge_sort<T: Ord+Copy>(arr:&mut [T]) {
if arr.len() > 1 {
let mid:usize = arr.len() / 2;
// Sort the left half recursively
top_down_merge_sort(&mut arr[..mid]);
// Sort the right half recursively
top_down_merge_sort(&mut arr[mid..]);
// Combine the two halves
merge(arr,mid)
}
}
#[cfg(test)]
mod tests {
#[cfg(test)]
mod top_down_merge_sort {
use super::super::*;
#[test]
fn basic() {
let mut res = vec![10,3,8,2,7,6,1,4,5,9];
top_down_merge_sort(&mut res);
assert_eq!(res, vec![1,2,3,4,5,6,7,8,9,10])
}
#[test]
fn basic_string() {
let mut res = vec!["a","bb","d","cc"];
top_down_merge_sort(&mut res);
assert_eq!(res,vec!("a","bb","cc","d"))
}
#[test]
fn empty() {
let mut res = Vec::<u8>::new();
top_down_merge_sort(&mut res);
assert_eq!(res, vec![])
}
#[test]
fn one_element() {
let mut res = vec![1];
top_down_merge_sort(&mut res);
assert_eq!(res, vec![1])
}
#[test]
fn pre_sorted() {
let mut res = vec![1,2,3,4,5,6,7];
top_down_merge_sort(&mut res);
assert_eq!(res, vec![1,2,3,4,5,6,7])
}
}
}