Last active
January 7, 2020 00:18
-
-
Save dbyr/8247f3d584656674745d6eceed023384 to your computer and use it in GitHub Desktop.
A first attempt by a beginner rustacean to create a generic sorting algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
mod sort { | |
fn insert_from_right<S>(vals: &mut [S], left: usize, right: usize) where S: Clone { | |
let mut i = right; | |
let mut temp; | |
while i > left { | |
temp = vals[i].clone(); | |
vals[i] = vals[i - 1].clone(); | |
vals[i - 1] = temp; | |
i -= 1; | |
} | |
} | |
fn sort_slice<S>(vals: &[S], result: &mut [S], order: &Fn(&S, &S) -> i8) -> bool | |
where S: Clone { | |
let vals_len = vals.len(); | |
let mut mid = vals_len / 2; | |
let mut l_i = 0; | |
let mut r_i = mid; | |
// base case | |
if vals_len != result.len() { | |
return false; | |
} else if vals_len == 0 { | |
return true; | |
} else if vals_len == 1 { | |
result[0] = vals[0].clone(); | |
return true; | |
} | |
// recursively sort the vector | |
let mut success = sort_slice(&vals[0..mid], &mut result[0..mid], order); | |
success &= sort_slice(&vals[mid..vals_len], &mut result[mid..vals_len], order); | |
if !success { | |
return success; | |
} | |
// sort the two halves into a full vector | |
while l_i < mid && r_i < vals_len { | |
let comp = order(&result[l_i], &result[r_i]); | |
if comp > 0 { | |
insert_from_right(&mut result[..], l_i, r_i); | |
mid += 1; | |
r_i += 1; | |
} | |
l_i += 1; | |
} | |
true | |
} | |
pub fn sort<S>(vals: &Vec<S>, order: &Fn(&S, &S) -> i8) -> Option<Vec<S>> where S: Clone { | |
let mut result; | |
if vals.len() == 0 { | |
return Some(vec![]); | |
} else { | |
result = vec![vals[0].clone(); vals.len()]; | |
} | |
if sort_slice(&vals[..], &mut result[..], order) { | |
return Some(result); | |
} else { | |
return None; | |
} | |
} | |
} | |
use sort::sort; | |
fn main() { | |
let start = vec![5, 2, 6, 10, 1, 0, 11, 3]; | |
let small_to_large = sort(&start, | |
&|left, right| -> i8 { | |
if left < right { | |
-1 | |
} else if left == right { | |
0 | |
} else { | |
1 | |
} | |
} | |
); | |
let large_to_small = sort(&start, | |
&|left, right| -> i8 { | |
if left < right { | |
1 | |
} else if left == right { | |
0 | |
} else { | |
-1 | |
} | |
} | |
); | |
match small_to_large { | |
Some(res) => println!("{:?}", &res), | |
None => println!("Could not perform sort"), | |
} | |
match large_to_small { | |
Some(res) => println!("{:?}", &res), | |
None => println!("Could not perform sort"), | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Moved from requiring a trait to allowing the user to define their own sorting criteria (comparison method).