Rust implementations of all the algorithms found in the book "Grokking Algorithms"

grokking-algorithms-1.rs

//! Chapter 1: Introduction to Algorithms. Binary Search.

// NB: input must be sorted
fn binary_search<T>(lst: &[T], item: &T) -> Option<usize>
where T: PartialEq + PartialOrd
{
    let mut low = 0;
    let mut high = lst.len() - 1;
    
    while low <= high {
        let mid = low + high;
        let guess = &lst[mid];
        
        if guess == item {
            return Some(mid);
        }
        
        if guess > item {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    None
}

fn main() {
    let mut v = vec!["foo", "bar", "baz", "quux", "bing"];
    let q = v.clone();
    v.sort();
    
    for s in q.iter() {
        println!("Looking for {}", s);
        if let Some(idx) = binary_search(&v, s) {
            println!("{} was found at index {}", v[idx], idx);
        } else {
            println!("Item could not be found");
        }
    }
}

grokking-algorithms-2.rs

//! Chapter 2: Selection Sort.

fn find_smallest<T>(arr: &[T]) -> usize
where
    T: PartialEq + PartialOrd,
{
    let mut smallest = &arr[0];
    let mut smallest_index = 0;

    for i in 1..arr.len() {
        if arr[i] < *smallest {
            smallest = &arr[i];
            smallest_index = i;
        }
    }

    smallest_index
}

fn selection_sort<T>(arr: &[T]) -> Vec<T>
where
    T: PartialEq + PartialOrd + Clone,
{
    let mut arr = arr.to_vec(); // ensures the original won't get destroyed
    let mut new_arr = Vec::new();
    for _ in 0..arr.len() {
        let smallest = find_smallest(&arr);
        new_arr.push(arr.remove(smallest))
    }

    new_arr
}

fn main() {
    let v = vec!["foo", "bar", "baz", "quux", "bing"];
    let new_v = selection_sort(&v);
    println!("old: {:?}\nnew: {:?}", v, new_v)
}