Rust Cheat Sheet

Bubble sort

fn bubble_sort<T: Ord + Copy>(mut list: Vec<T>) -> Vec<T> {
    for i in 0 .. list.len() {
        for j in i .. list.len() {
            if list[i] > list[j] {
                list.swap(i, j);
            }
        }
    }

    return list;
}

Merge sort

fn merge_sort<T: Ord + Copy>(list: Vec<T>) -> Vec<T> {
    if list.len() > 1 {
        let middle = list.len() / 2;

        let l = merge_sort(list[..middle].to_vec());
        let r = merge_sort(list[middle..].to_vec());

        return merge(l, r)
    }

    return list
}

fn merge<T: Ord + Copy>(mut l: Vec<T>, mut r: Vec<T>) -> Vec<T> {
    let mut new_vec = vec![];

    while l.len() > 0 && r.len() > 0 {
        if l[0] < r[0] {
            new_vec.push(l.remove(0));
        } else {
            new_vec.push(r.remove(0));
        }
    }

    new_vec.append(&mut l);
    new_vec.append(&mut r);

    return new_vec;
}

Quicksort (Hoare partition scheme)

fn quicksort<T: Ord + Copy>(vector: &mut [T]) -> &[T] {
    if vector.len() > 1 {
        let p = partition(vector);

        quicksort(&mut vector[..p]);
        quicksort(&mut vector[p..]);
    }
    return vector;
}

fn partition<T: Ord + Copy>(vector: &mut [T]) -> usize {
    let (mut left, mut right) = (0, vector.len()-1);
    let pivot = vector[vector.len() / 2];

    loop {
        while vector[left] < pivot {
            left+=1;
        }

        while vector[right] > pivot {
            right-=1;
        }

        if left >= right {
            break;
        }

        vector.swap(left, right)
    }

    return right
}