rust sort - Forest0923/memo GitHub Wiki

use std::io;
use rand::seq::SliceRandom;

fn bubble(v: &mut Vec<u32>) {
    //println!("{:?}", v);
    let l = v.len();
    for i in 0..l {
        for j in ((0+i+1)..l).rev() {
            let j = j as usize;
            if v[j] < v[j - 1] {
                v.swap(j, j - 1);
            }
        }
    }
}

fn selection(v: &mut Vec<u32>) {
    //println!("{:?}", v);
    let l = v.len();
    let mut min: usize;
    for i in 0..l {
        min = i as usize;
        for j in (i+1)..l {
            let j = j as usize;
            if v[j] < v[min] {
                min = j;
            }
        }
        v.swap(i as usize, min);
    }
}

fn insertion(v: &mut Vec<u32>) {
    let l = v.len();
    for i in 1..l {
        for j in (1..(i+1)).rev() {
            let j = j as usize;
            if v[j] < v[j-1] {
                v.swap(j, j-1);
            }
        }
    }
}

fn heap(v: &mut Vec<u32>) {
    /*
     *     n
     *    / \
     *   /   \
     * 2n+1  2n+2
     */
    let l = v.len();
    let mut node: usize;
    for i in 0..l {
        node = i as usize;
        while node > 0 {
            if v[node] > v[(node-1)/2] {
                v.swap(node, (node-1)/2);
                node = (node-1)/2;
            } else {
                break;
            }
        }
    }
    for i in (0..l).rev() {
        let i = i as usize;
        v.swap(0, i);
        node = 0;
        // If child node exists ...
        while node * 2 + 1 < i {
            if node * 2 + 2 == i {
                if v[node] < v[node * 2 + 1] {
                    v.swap(node, node * 2 + 1);
                    node = node * 2 + 1;
                } else {
                    break;
                }
            } else {
                if v[node * 2 + 1] < v[node * 2 + 2] {
                    if v[node] < v[node * 2 + 2] {
                        v.swap(node, node * 2 + 2);
                        node = node * 2 + 2;
                    } else {
                        break;
                    }
                } else if v[node * 2 + 1] > v[node * 2 + 2] {
                    if v[node] < v[node * 2 + 1] {
                        v.swap(node, node * 2 + 1);
                        node = node * 2 + 1;
                    } else {
                        break;
                    }
                }
            }
        }
    }
}

fn merge(v: &mut Vec<u32>, left: &mut Vec<u32>, right: &mut Vec<u32>) {
    let mut v_head = 0;
    let mut l_head = 0;
    let mut r_head = 0;
    while l_head < left.len() && r_head < right.len() {
        if left[l_head] < right[r_head] {
            v[v_head] = left[l_head];
            v_head += 1;
            l_head += 1;
        } else {
            v[v_head] = right[r_head];
            v_head += 1;
            r_head += 1;
        }
    }
    while l_head < left.len() {
        v[v_head] = left[l_head];
        v_head += 1;
        l_head += 1;
    }
    while r_head < right.len() {
        v[v_head] = right[r_head];
        v_head += 1;
        r_head += 1;
    }
}

fn merge_sort(v: &mut Vec<u32>) {
    let l = v.len();
    let mut left: Vec<u32> = v[0..l/2].to_vec();
    let mut right: Vec<u32> = v[l/2..l].to_vec();
    if l == 1 {
        return;
    } else {
        merge_sort(&mut left);
        merge_sort(&mut right);
        merge(v, &mut left, &mut right);
    }
}

fn quick_sort(v: &mut Vec<u32>, left: usize, right: usize) {
    if left == right {
        return;
    }
    let pivot = right;
    let mut l_head = left;
    let mut r_head = right - 1;
    loop {
        while v[l_head] < v[pivot] {
            l_head += 1;
        }
        while v[pivot] < v[r_head] && l_head < r_head {
            r_head -= 1;
        }
        if l_head < r_head {
            v.swap(l_head, r_head);
            l_head += 1;
        } else {
            v.swap(l_head, pivot);
            break;
        }
    }
    if l_head == r_head && l_head == left {
        quick_sort(v, l_head+1, right);
    } else if l_head == r_head {
        quick_sort(v, left, l_head-1);
        quick_sort(v, l_head+1, right);
    } else {
        quick_sort(v, left, l_head-1);
    }
}

fn quick_sort_wrapper(v: &mut Vec<u32>) {
    if v.len() < 1 {
        return;
    }
    quick_sort(v, 0, v.len()-1);
}

const BUF_SIZE: u32 = 20;

fn main() {
    let mut rng = rand::thread_rng();
    let mut v: Vec<u32> = (0..BUF_SIZE).collect();
    v.shuffle(&mut rng);
    //let mut v: Vec<u32> = [3,2,0,1,4].to_vec();
    println!("Please select sort method:");
    println!("  Bubble sort     -> 0");
    println!("  Selection sort  -> 1");
    println!("  Insertion sort  -> 2");
    println!("  Heap sort       -> 3");
    println!("  Merge sort      -> 4");
    println!("  Quick sort      -> 5");
    let mut sort_method = String::new();
    io::stdin().read_line(&mut sort_method)
        .expect("Failed to read line");
    let sort_method: u32 = match sort_method.trim().parse() {
        Ok(num) => num,
        Err(_)  => {
            println!("Please input valid number");
            return;
        }
    };
    println!("Original: {:?}", v);
    match sort_method {
        0   => {
            println!("Bubble sort");
            bubble(&mut v);
        },
        1   => {
            println!("Selection sort");
            selection(&mut v);
        },
        2   => {
            println!("Insertion sort");
            insertion(&mut v);
        },
        3   => {
            println!("Heap sort");
            heap(&mut v);
        },
        4   => {
            println!("Merge sort");
            merge_sort(&mut v);
        },
        5   => {
            println!("Quick sort");
            quick_sort_wrapper(&mut v);
        },
        _   => {
            println!("Please input valid number");
            return;
        }
    }
    println!("Sorted:   {:?}", v);
}