3
\$\begingroup\$

I have written some sorting algorithms in Rust and wanted to see how terrible they were.

What I am looking for:

  1. Bugs
  2. Performance improvements
  3. Idiomatic code
  4. Maybe even a functional approach to the sorting algos
  5. Why is the merge sort so slow? Is it my implementation?

Note you will need rand = '*' in your Cargo.toml for running tests/benches. All tests pass at this point and here are the benches from my machine.

test tests::bench_large_bubble_sort    ... bench:   1,294,490 ns/iter (+/- 188,917)
test tests::bench_large_merge_sort     ... bench:   1,196,096 ns/iter (+/- 141,654)
test tests::bench_large_quick_sort     ... bench:      70,173 ns/iter (+/- 11,150)
test tests::bench_large_selection_sort ... bench:   1,351,724 ns/iter (+/- 197,069)
test tests::bench_large_shell_sort     ... bench:      95,080 ns/iter (+/- 14,972)
test tests::bench_small_bubble_sort    ... bench:         923 ns/iter (+/- 118)
test tests::bench_small_merge_sort     ... bench:       4,479 ns/iter (+/- 743)
test tests::bench_small_quick_sort     ... bench:         824 ns/iter (+/- 103)
test tests::bench_small_selection_sort ... bench:         788 ns/iter (+/- 129)
test tests::bench_small_shell_sort     ... bench:         852 ns/iter (+/- 117)

#![feature(test)]
#![feature(step_by)]

fn selection_sort(mut values: Vec<i32>) -> Vec<i32> {
    let mut min;
    for outer in 0..values.len() {
        min = outer;
        for inner in (outer + 1)..values.len() {
            if values[inner] < values[min] {
                min = inner;
            }
        }
        let temp = values[outer];
        values[outer] = values[min];
        values[min] = temp;
    }
    return values;
}

fn bubble_sort(mut values: Vec<i32>) -> Vec<i32> {
    let mut swapped = true;
    let mut j = 0;
    while swapped {
        swapped = false;
        j += 1;
        for inner in 0..(values.len() - j) {
            if values[inner] > values[inner + 1] {
                let tmp = values[inner];
                values[inner] = values[inner + 1];
                values[inner + 1] = tmp;
                swapped = true;
            }
        }
    }
    return values;
}

fn quick_sort(mut values: &mut Vec<i32>, start: Option<isize>, end: Option<isize>) {

    fn partition(mut partition_values: &mut Vec<i32>, start: isize, end: isize) -> isize {
        let mut pivot = start;
        for idx in (start + 1)..(end + 1) {
            if partition_values[idx as usize] <= partition_values[start as usize] {
                pivot += 1;
                let tmp = partition_values[idx as usize];
                partition_values[idx as usize] = partition_values[pivot as usize];
                partition_values[pivot as usize] = tmp;
            }
        }
        let tmp = partition_values[start as usize];
        partition_values[start as usize] = partition_values[pivot as usize];
        partition_values[pivot as usize] = tmp;
        return pivot;
    }

    let start_val = start.unwrap_or(0);
    let end_val = end.unwrap_or((values.len() - 1) as isize);
    if start_val >= end_val {
        return;
    }
    let pivot = partition(values, start_val, end_val);
    quick_sort(values, Some(start_val), Some(pivot - 1));
    quick_sort(values, Some(pivot + 1), Some(end_val));
}

fn shell_sort(mut values: &mut Vec<i32>) {
    fn sort_gap_insertation(mut values: &mut Vec<i32>, start: usize, gap: usize) {
        for i in ((start + gap)..values.len()).step_by(gap) {
            let val_current = values[i];
            let mut pos = i;

            while pos >= gap && values[pos - gap] > val_current {
                values[pos] = values[pos - gap];
                pos = pos - gap;
            }
            values[pos] = val_current;
        }
    }

    let mut count_sublist = values.len() / 2;
    while count_sublist > 0 {
        for pos_start in 0..count_sublist {
            sort_gap_insertation(values, pos_start, count_sublist);
        }
        count_sublist /= 2;
    }

}

fn merge_sort(values: Vec<i32>) -> Vec<i32> {
    fn merge(left: Vec<i32>, right: Vec<i32>) -> Vec<i32> {
        if left.len() == 0 {
            return right;
        }
        if right.len() == 0 {
            return left;
        }
        if left[0] < right[0] {
            let mut v = Vec::new();
            v.push(left[0]);
            v.extend(merge(left[1..].to_vec(), right));
            return v;
        }
        let mut v = Vec::new();
        v.push(right[0]);
        v.extend(merge(left, right[1..].to_vec()));
        return v;
    }

    if values.len() <= 1 {
        return values;
    }
    let mid = values.len() / 2;
    let left = merge_sort(values[..mid].to_vec());
    let right = merge_sort(values[mid..].to_vec());
    return merge(left, right);
}

fn main() {
    let v = vec![3, 2, 1];
    println!("{:?}", selection_sort(v));
    let v = vec![1, 1, 2, 3, 1, 5, 6, 6, 10, 1000, 10000, 5, 6, 6, 12];
    println!("{:?}", selection_sort(v));

    let v = vec![3, 2, 1];
    println!("{:?}", bubble_sort(v));
    let v = vec![1, 1, 2, 3, 1, 5, 6, 6, 10, 1000, 10000, 5, 6, 6, 12];
    println!("{:?}", bubble_sort(v));

    let mut v = vec![1, 5, 1, 5, 6, 0, 10, -5];
    quick_sort(&mut v, None, None);
    println!("{:?}", v);

    let mut v = vec![1, 5, 1, 5, 6, 0, 10, -5];
    shell_sort(&mut v);
    println!("{:?}", v);

    let v = vec![1, 5, 1, 5, 6, 0, 10, -5];
    println!("{:?}", merge_sort(v));

}

#[cfg(test)]
extern crate test;
#[cfg(test)]
extern crate rand;

#[cfg(test)]
mod tests {
    use test::Bencher;
    use rand::{self, Rng};

    #[test]
    fn test_selection_sort() {
        let mut rng = rand::thread_rng();
        let v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
        let result = super::selection_sort(v);
        for i in 0..result.len() - 1 {
            assert!(result[i] <= result[i + 1]);
        }
    }

    #[bench]
    fn bench_large_selection_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
            super::selection_sort(v);
        })
    }

    #[bench]
    fn bench_small_selection_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let v: Vec<i32> = rng.gen_iter::<i32>().take(15).collect();
            super::selection_sort(v);
        })
    }

    #[test]
    fn test_bubble_sort() {
        let mut rng = rand::thread_rng();
        let v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
        let result = super::bubble_sort(v);
        for i in 0..result.len() - 1 {
            assert!(result[i] <= result[i + 1])
        }
    }

    #[bench]
    fn bench_large_bubble_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
            super::bubble_sort(v);
        })
    }

    #[bench]
    fn bench_small_bubble_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let v: Vec<i32> = rng.gen_iter::<i32>().take(15).collect();
            super::bubble_sort(v);
        })
    }

    #[test]
    fn test_quick_sort() {
        let mut rng = rand::thread_rng();
        let mut v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
        super::quick_sort(&mut v, None, None);
        for i in 0..v.len() - 1 {
            assert!(v[i] <= v[i + 1]);
        }
    }

    #[bench]
    fn bench_large_quick_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let mut v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
            super::quick_sort(&mut v, None, None);
        })
    }

    #[bench]
    fn bench_small_quick_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let mut v: Vec<i32> = rng.gen_iter::<i32>().take(15).collect();
            super::quick_sort(&mut v, None, None);
        })
    }

    #[test]
    fn test_shell_sort() {
        let mut rng = rand::thread_rng();
        let mut v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
        super::shell_sort(&mut v);
        for i in 0..v.len() - 1 {
            assert!(v[i] <= v[i + 1]);
        }
    }

    #[bench]
    fn bench_large_shell_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let mut v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
            super::shell_sort(&mut v);
        })
    }

    #[bench]
    fn bench_small_shell_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let mut v: Vec<i32> = rng.gen_iter::<i32>().take(15).collect();
            super::shell_sort(&mut v);
        })
    }

    #[test]
    fn test_merge_sort() {
        let mut rng = rand::thread_rng();
        let v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
        let result = super::merge_sort(v);
        for i in 0..result.len() - 1 {
            assert!(result[i] <= result[i + 1]);
        }
    }

    #[bench]
    fn bench_large_merge_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
            super::merge_sort(v);
        })
    }

    #[bench]
    fn bench_small_merge_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let v: Vec<i32> = rng.gen_iter::<i32>().take(15).collect();
            super::merge_sort(v);
        })
    }
}

I have also created a version of this using traits instead of free functions. I wasn't able to get merge_sort working yet but here are the rest.

#![feature(test)]
#![feature(step_by)]
use std::cmp::Ord;
use std::clone::Clone;

trait SelectSortable {
    fn selection_sort(&mut self);
}

impl<T: Ord + Clone + PartialEq> SelectSortable for Vec<T> {
    fn selection_sort(&mut self) {
        let mut min;
        for outer in 0..self.len() {
            min = outer;
            for inner in (outer + 1)..self.len() {
                if self[inner] < self[min] {
                    min = inner;
                }
            }
            let temp = self[outer].clone();
            self[outer] = self[min].clone();
            self[min] = temp;
        }
    }
}

trait BubbleSortable {
    fn bubble_sort(&mut self);
}

impl<T: Ord + Clone + PartialEq> BubbleSortable for Vec<T> {
    fn bubble_sort(&mut self) {
        let mut swapped = true;
        let mut j = 0;
        while swapped {
            swapped = false;
            j += 1;
            for inner in 0..(self.len() - j) {
                if self[inner] > self[inner + 1] {
                    let temp = self[inner].clone();
                    self[inner] = self[inner + 1].clone();
                    self[inner + 1] = temp;
                    swapped = true;
                }
            }
        }
    }
}

trait QuickSortable {
    fn quick_sort(&mut self, start: Option<isize>, end: Option<isize>);
    fn _partition(&mut self, start: isize, end: isize) -> isize;
}

impl<T: Ord + Clone + PartialEq> QuickSortable for Vec<T> {
    fn _partition(&mut self, start: isize, end: isize) -> isize {
        let mut pivot = start;
        for idx in (start + 1)..(end + 1) {
            if self[idx as usize] <= self[start as usize] {
                pivot += 1;
                let tmp = self[idx as usize].clone();
                self[idx as usize] = self[pivot as usize].clone();
                self[pivot as usize] = tmp;
            }
        }
        let tmp = self[start as usize].clone();
        self[start as usize] = self[pivot as usize].clone();
        self[pivot as usize] = tmp;
        return pivot;
    }


    fn quick_sort(&mut self, start: Option<isize>, end: Option<isize>) {

        let start_val = start.unwrap_or(0);
        let end_val = end.unwrap_or((self.len() - 1) as isize);
        if start_val >= end_val {
            return;
        }
        let pivot = self._partition(start_val, end_val);
        self.quick_sort(Some(start_val), Some(pivot - 1));
        self.quick_sort(Some(pivot + 1), Some(end_val));
    }
}

trait ShellShortable {
    fn shell_sort(&mut self);
    fn _gap_insert(&mut self, start: usize, gap: usize);
}

impl<T: Ord + Clone + PartialEq> ShellShortable for Vec<T> {
    fn _gap_insert(&mut self, start: usize, gap: usize) {
        for i in ((start + gap)..self.len()).step_by(gap) {
            let val_current = self[i].clone();
            let mut pos = i;

            while pos >= gap && self[pos - gap] > val_current {
                self[pos] = self[pos - gap].clone();
                pos = pos - gap;
            }
            self[pos] = val_current;
        }
    }

    fn shell_sort(&mut self) {
        let mut count_sublist = self.len() / 2;
        while count_sublist > 0 {
            for pos_start in 0..count_sublist {
                self._gap_insert(pos_start, count_sublist);
            }
            count_sublist /= 2;
        }

    }
}


fn main() {
    let mut v = vec![3, 2, 1];
    v.selection_sort();
    println!("{:?}", v);

    let mut v = vec![3, 2, 1];
    v.bubble_sort();
    println!("{:?}", v);
    let mut v = vec![1, 1, 2, 3, 1, 5, 6, 6, 10, 1000, 10000, 5, 6, 6, 12];
    v.bubble_sort();
    println!("{:?}", v);

    let mut v = vec![1, 5, 1, 5, 6, 0, 10, -5];
    v.quick_sort(None, None);
    println!("{:?}", v);

    let mut v = vec![1, 5, 1, 5, 6, 0, 10, -5];
    v.shell_sort();
    println!("{:?}", v);
}

#[cfg(test)]
extern crate test;
#[cfg(test)]
extern crate rand;

#[cfg(test)]
mod tests {
    use test::Bencher;
    use rand::{self, Rng};
    use super::{SelectSortable, BubbleSortable, QuickSortable, ShellShortable};

    #[test]
    fn test_selection_sort() {
        let mut rng = rand::thread_rng();
        let mut v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
        v.selection_sort();
        for i in 0..v.len() - 1 {
            assert!(v[i] <= v[i + 1]);
        }
    }

    #[bench]
    fn bench_large_selection_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let mut v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
            v.selection_sort();
        })
    }

    #[bench]
    fn bench_small_selection_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let mut v: Vec<i32> = rng.gen_iter::<i32>().take(15).collect();
            v.selection_sort();
        })
    }

    #[test]
    fn test_bubble_sort() {
        let mut rng = rand::thread_rng();
        let mut v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
        v.bubble_sort();
        for i in 0..v.len() - 1 {
            assert!(v[i] <= v[i + 1])
        }
    }

    #[bench]
    fn bench_large_bubble_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let mut v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
            v.bubble_sort();
        })
    }

    #[bench]
    fn bench_small_bubble_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let mut v: Vec<i32> = rng.gen_iter::<i32>().take(15).collect();
            v.bubble_sort();
        })
    }

    #[test]
    fn test_quick_sort() {
        let mut rng = rand::thread_rng();
        let mut v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
        v.quick_sort(None, None);
        for i in 0..v.len() - 1 {
            assert!(v[i] <= v[i + 1]);
        }
    }

    #[bench]
    fn bench_large_quick_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let mut v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
            v.quick_sort(None, None);
        })
    }

    #[bench]
    fn bench_small_quick_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let mut v: Vec<i32> = rng.gen_iter::<i32>().take(15).collect();
            v.quick_sort(None, None);
        })
    }

    #[test]
    fn test_shell_sort() {
        let mut rng = rand::thread_rng();
        let mut v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
        v.shell_sort();
        for i in 0..v.len() - 1 {
            assert!(v[i] <= v[i + 1]);
        }
    }

    #[bench]
    fn bench_large_shell_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let mut v: Vec<i32> = rng.gen_iter::<i32>().take(1000).collect();
            v.shell_sort();
        })
    }

    #[bench]
    fn bench_small_shell_sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = rand::thread_rng();
            let mut v: Vec<i32> = rng.gen_iter::<i32>().take(15).collect();
            v.shell_sort();
        })
    }
}
\$\endgroup\$
4
\$\begingroup\$

The merge function in your merge sort is \$\mathcal{O}(n^2)\$ (it's meant to be \$\mathcal{O}(n)\$) because

v.extend(merge(left[1..].to_vec(), right));

uses extend, which takes \$\mathcal{O}(n)\$ time, and you do it \$\mathcal{O}(n)\$ times, which makes \$\mathcal{O}(n^2)\$ total.

The merge is normally implemented by pushing one element at a time to a mutable buffer.

| improve this answer | |
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.