Skip to content

Instantly share code, notes, and snippets.

@jmcph4 jmcph4/mergesort.rs
Created May 23, 2020

Embed
What would you like to do?
Bugged mergesort implementation in Rust
use std::fmt::{Display, Debug};
use crate::error::EnceladusError;
use crate::list::List;
pub fn mergesort<L, T>(list: &mut L) -> Result<(), EnceladusError>
where L: List<T>, T: Eq + PartialOrd + Clone + Display + Debug {
if list.length()? <= 1 {
return Ok(());
}
//mergesort_range(list, 0, list.length()?)?;
let middle: usize = list.length()? / 2;
merge(list, 0, middle, list.length()? - 1)?;
Ok(())
}
pub fn mergesort_range<L, T>(list: &mut L, start: usize, end: usize) ->
Result<(), EnceladusError> where L: List<T>,
T: Eq + PartialOrd + Clone + Display + Debug {
if start < end {
let middle: usize = (start + end) / 2;
mergesort_range(list, start, middle)?;
mergesort_range(list, middle + 1, end)?;
merge(list, start, middle, end)?;
}
Ok(())
}
pub fn merge<L, T>(list: &mut L, start: usize, middle: usize, end: usize) ->
Result<(), EnceladusError> where L: List<T>, T: Eq + PartialOrd + Clone +
Display + Debug {
println!("MERGE {} {} {}", start, middle, end); // DEBUG
let left_len: usize = middle - start + 1;
let right_len: usize = end - middle;
let mut left_sublist: Vec<T> = Vec::new();
let mut right_sublist: Vec<T> = Vec::new();
for i in 0..left_len {
left_sublist.push(list.get(start + i)?.clone());
}
for i in 0..right_len {
right_sublist.push(list.get(middle + 1 + i)?.clone());
}
let mut i: usize = 0;
let mut j: usize = 0;
for k in start..=end {
if i >= left_len {
list.set(k, right_sublist[j].clone())?;
j += 1;
} else if j >= right_len {
list.set(k, left_sublist[i].clone())?;
i += 1;
} else {
if left_sublist[i] <= right_sublist[j] {
list.set(k, left_sublist[i].clone())?;
i += 1;
} else {
list.set(k, right_sublist[j].clone())?;
j += 1;
}
}
}
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
use crate::arraylist::ArrayList;
#[test]
pub fn test_mergesort_normal1() -> Result<(), EnceladusError> {
let mut actual_list: ArrayList<u64> = ArrayList::new();
actual_list.append(33)?;
actual_list.append(12)?;
actual_list.append(0)?;
actual_list.append(1)?;
actual_list.append(4)?;
let mut expected_list: ArrayList<u64> = ArrayList::new();
expected_list.append(0)?;
expected_list.append(1)?;
expected_list.append(4)?;
expected_list.append(12)?;
expected_list.append(33)?;
let actual_res: Result<(), EnceladusError> =
mergesort(&mut actual_list);
let expected_res: Result<(), EnceladusError> = Ok(());
assert_eq!(actual_list, expected_list);
assert_eq!(actual_res, expected_res);
Ok(())
}
#[test]
pub fn test_mergesort_normal_empty() -> Result<(), EnceladusError> {
let mut actual_list: ArrayList<u64> = ArrayList::new();
let expected_list: ArrayList<u64> = ArrayList::new();
let actual_res: Result<(), EnceladusError> =
mergesort(&mut actual_list);
let expected_res: Result<(), EnceladusError> = Ok(());
assert_eq!(actual_list, expected_list);
assert_eq!(actual_res, expected_res);
Ok(())
}
#[test]
pub fn test_mergesort_normal_single() -> Result<(), EnceladusError> {
let mut actual_list: ArrayList<u64> = ArrayList::new();
actual_list.append(1)?;
let mut expected_list: ArrayList<u64> = ArrayList::new();
expected_list.append(1)?;
let actual_res: Result<(), EnceladusError> =
mergesort(&mut actual_list);
let expected_res: Result<(), EnceladusError> = Ok(());
assert_eq!(actual_list, expected_list);
assert_eq!(actual_res, expected_res);
Ok(())
}
#[test]
pub fn test_mergesort_normal_sorted_two_elems() ->
Result<(), EnceladusError> {
let mut actual_list: ArrayList<u64> = ArrayList::new();
actual_list.append(1)?;
actual_list.append(12)?;
let mut expected_list: ArrayList<u64> = ArrayList::new();
expected_list.append(1)?;
expected_list.append(12)?;
let actual_res: Result<(), EnceladusError> =
mergesort(&mut actual_list);
let expected_res: Result<(), EnceladusError> = Ok(());
assert_eq!(actual_list, expected_list);
assert_eq!(actual_res, expected_res);
Ok(())
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.