2017-08-29 08:08:42 +00:00
|
|
|
use sorting::Algorithm;
|
2017-08-27 16:52:51 +00:00
|
|
|
|
2017-08-29 08:08:42 +00:00
|
|
|
pub struct Sort;
|
2017-08-27 16:52:51 +00:00
|
|
|
|
2017-08-29 08:08:42 +00:00
|
|
|
impl Algorithm for Sort {
|
2017-08-27 16:52:51 +00:00
|
|
|
fn sort(mut vector: Vec<i32>) -> Result<Vec<i32>, &'static str> {
|
|
|
|
let pivot = match vector.pop() {
|
|
|
|
Some(v) => v,
|
|
|
|
None => return Ok(Vec::new()),
|
|
|
|
};
|
|
|
|
let mut pivots: Vec<i32> = Vec::new();
|
|
|
|
pivots.push(pivot);
|
|
|
|
|
|
|
|
let mut smaller: Vec<i32> = Vec::new();
|
|
|
|
let mut larger: Vec<i32> = Vec::new();
|
|
|
|
|
|
|
|
while vector.len() != 0 {
|
|
|
|
let element = match vector.pop() {
|
|
|
|
Some(v) => v,
|
|
|
|
None => {
|
|
|
|
return Err(
|
|
|
|
"Vector had a length not equal to 0, but still had no more element in it. This point should not be reachable.",
|
|
|
|
)
|
|
|
|
}
|
|
|
|
};
|
|
|
|
if element < pivot {
|
|
|
|
smaller.push(element);
|
|
|
|
} else if element > pivot {
|
|
|
|
larger.push(element);
|
|
|
|
} else {
|
|
|
|
pivots.push(element);
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
let mut result: Vec<i32> = Vec::new();
|
|
|
|
|
2017-08-29 08:08:42 +00:00
|
|
|
for v in match Sort::sort(smaller) {
|
2017-08-27 16:52:51 +00:00
|
|
|
Ok(v) => v,
|
|
|
|
Err(e) => return Err(e),
|
|
|
|
}
|
|
|
|
{
|
|
|
|
result.push(v);
|
|
|
|
}
|
|
|
|
|
|
|
|
for v in pivots {
|
|
|
|
result.push(v);
|
|
|
|
}
|
|
|
|
|
2017-08-29 08:08:42 +00:00
|
|
|
for v in match Sort::sort(larger) {
|
2017-08-27 16:52:51 +00:00
|
|
|
Ok(v) => v,
|
|
|
|
Err(e) => return Err(e),
|
|
|
|
}
|
|
|
|
{
|
|
|
|
result.push(v);
|
|
|
|
}
|
|
|
|
|
|
|
|
return Ok(result);
|
|
|
|
}
|
|
|
|
}
|