# Selection and Insertion sort in Rust

I have been learning programming for better half of a year now and recently started learning Rust. This is my attempt at implementing selection sort and insertion sort. Since I tried to implement both without mutating the argument, I am not sure if my implementation agrees with the definitions.

Selection sort:

fn selection_sort<T>(arr: &[T]) -> VecDeque<T>
where T: PartialOrd + Clone {
if arr.len() == 1 {
return VecDeque::from(arr.to_vec())
}
let mut sorted = selection_sort(&arr[1..]);
let el = arr[0].clone();
if el >= *sorted.back().unwrap(){
sorted.push_back(el);
} else if el <= *sorted.front().unwrap() {
sorted.push_front(el);
} else {
let mut max = sorted.len() - 1;
for i in 1..max {
if sorted[i]>el && sorted[i] <= sorted[max] {
max = i;
}
}
sorted.insert(max, el)
}
sorted
}


Insertion sort:

fn insertion_sort <T>(arr: &[T]) -> Vec<T>
where T: PartialOrd + Clone {
let mut sorted = vec![arr[0].clone()];
for i in 1..arr.len() {
sorted.push(arr[i].clone());
let mut j = i;
while j > 0 && sorted[j] < sorted[j - 1 ] {
sorted.swap(j, j -1);
j = j - 1;
}
}
sorted
}

• Usually when people want to sort an array they want it sorted in place. Rust's standard sort takes a &mut slice. – ratchet freak Jul 7 '17 at 8:46
• @ratchetfreak Oh alright. Thanks. I didn't know that. :D – codeNoob Jul 7 '17 at 9:07