1
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.